Loopsspec

Alias Analysis

Can these two references point to the same memory? Almost every optimization over memory is gated on that question, the honest answer is usually "maybe", and "maybe" means no. Aliasing is the single biggest limiter on what a compiler is allowed to do.

The question

Why does the compiler keep reloading a value from memory when nothing visibly writes to it?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

IR over memory operations — loads and stores addressed by pointer values — together with an alias oracle: a function that, given two memory references, answers *must alias*, *may alias* or *no alias*. That three-valued answer is the representation this analysis contributes, and every memory optimization in the compiler is written against it. The middle answer is the one that does the damage, because it forbids everything the definite answers would allow.

What this phase may assume or do

This lesson is an analysis rather than a transformation, so the condition runs the other way: every transformation that moves, removes, reorders or reuses a memory access must first ask the oracle and may act only on a definite answer. A pass that treats *may alias* as *no alias* is not aggressive, it is wrong — and the resulting bug is a stale or clobbered value observed far from the transformation, with no crash.

Key points

  • The oracle answers must-alias, may-alias or no-alias, and only the definite answers permit a transformation. "Maybe" forbids.
  • Almost every memory optimization — load reuse, store elimination, hoisting, reordering, vectorization — is gated on this analysis.
  • The cheap answers come from address reasoning and escape analysis; the expensive ones from interprocedural points-to; the strongest from language guarantees.
  • Strict aliasing lets a C compiler assume unrelated types do not overlap, and reinterpreting casts violate it — undefined behavior that manifests only at higher optimization levels.
  • restrict transfers the proof obligation to the programmer with no checking; Rust's &mut makes the same guarantee and checks it.
  • Supplying aliasing information is often worth more than any hand transformation, because it unlocks several optimizations at once.

Why "maybe" costs so much

Consider a loop that writes through one pointer and reads through another. If the two might be the same, the read must happen after each write, the read cannot be hoisted, the loop cannot be vectorized, and every load must be re-executed. If they definitely differ, all of those become available at once. The entire difference in generated code comes from one bit of information the compiler could not derive.

This is why a C function taking two pointers of the same type produces conservative code and why the identical function in Fortran, whose arrays cannot alias, produces good code. It is the historical reason Fortran outperformed C on numerical work for decades — not a difference in compiler quality, but a difference in what the language allowed the compiler to assume.

The example below is the smallest complete demonstration. The reload of *n is not the compiler being timid; it is the compiler being correct, because p and n are both int* and the store through p may modify *n.

The reload that cannot be removed, and the annotation that removes it
Before
void scale(int *p, int *n) {
    for (int i = 0; i < *n; i++)
        p[i] *= 2;
}
// *n is re-loaded every iteration: p[i] may BE n.
After
void scale(int * restrict p, int * restrict n) {
    for (int i = 0; i < *n; i++)
        p[i] *= 2;
}
// *n is now loop-invariant and hoisted.
Legal only when

restrict on a pointer parameter is a promise that, for the lifetime of the pointer, the object it points to is accessed only through pointers derived from it. Given that promise for both parameters, a store through p cannot modify *n, so *n is loop-invariant and may be hoisted into the preheader — see [[loop-invariant-code-motion]].

Illegal when

The promise is false. Call scale(&x, &x) on restrict pointers and the behavior is undefined: the compiler has hoisted a load whose value the loop then modifies, and the loop's trip count is now whatever *n was on entry. There is no diagnostic and no crash — the program simply computes something else. restrict is a proof obligation transferred to the programmer, which is why it is powerful and why it is dangerous.

Where the answers come from

Alias analyses form a hierarchy from cheap and imprecise to expensive and precise, and real compilers run several and combine their answers, taking the most precise definite answer available.

Address-based reasoning is the cheapest and often the most effective: two accesses to distinct local variables whose addresses never escape cannot alias; two accesses at different constant offsets from the same base cannot alias; a pointer to freshly allocated memory cannot alias anything that existed before. Most of the useful answers in ordinary code come from this level, which is why [[escape-analysis]] is such a strong enabler.

Type-based alias analysis uses the language's rule that objects of unrelated types do not overlap. In C and C++ this is the *strict aliasing* rule: accessing an object through an lvalue of an incompatible type is undefined behavior, so the compiler is entitled to assume an int* and a float* do not alias. This is genuinely useful and it is also the source of a well-known class of bug, discussed below.

Flow-sensitive and interprocedural points-to analysis computes, for each pointer, the set of memory objects it may point to, propagated across the whole program. Andersen's formulation is more precise and roughly cubic; Steensgaard's is nearly linear and much coarser. Compilers use them where they can afford to and fall back to the cheaper rules where they cannot.

Programmer assertions — restrict in C, noalias in LLVM IR, __restrict in C++ compilers as an extension, #pragma ivdep — supply the answer directly. They are unverified: the compiler trusts them and the program is undefined if they are wrong.

Where each language gets its aliasing answersspec
LanguageWhat the compiler may assumeHow it goes wrong
C / C++specDistinct types do not alias (strict aliasing); restrict pointers do not aliasType-punning through a cast violates the assumption; the code works at -O0 and breaks at -O2
FortranspecDummy arguments do not alias unless explicitly aliasedAliasing them anyway is nonconforming, and the historic reason Fortran numerics outperformed C
Rustspec&mut T is unique for its lifetime — a stronger restrict, checked by the compilerOnly through unsafe code that violates the aliasing model
Java / C#specNo pointer arithmetic; references of unrelated class types cannot aliasArrays of a supertype can hold subtypes, so array element aliasing is still a live question
SwiftimplementationExclusive access to inout parameters, enforced statically and at run timeOverlapping access is trapped rather than silently miscompiled
AtlasLangimplementationNo pointers at all, so aliasing does not ariseNot applicable — which is why its optimizer needs no alias analysis and cannot demonstrate this lesson

Strict aliasing: the rule that pays for itself and bites

specStrict aliasing is a C and C++ language rule, not a compiler heuristic; violating it is undefined behavior with no required diagnostic. GCC enables -fstrict-aliasing at -O2 and above and offers -Wstrict-aliasing (which catches only the most obvious cases). Rust, Java and C# have no equivalent hazard because their type systems do not permit the reinterpreting cast that creates it — see [[ub-and-optimization]].

The C and C++ standards say that an object may be accessed only through an lvalue of a compatible type — with a short list of exceptions, notably char and, in C, a union member. The rule exists so the compiler can assume that a write through a float* does not disturb a value read through an int*, which is worth a great deal in numerical code.

The classic violation is reinterpreting bits by casting a pointer: taking the address of a float, casting it to int*, and reading through it to inspect the exponent. This is undefined behavior. It usually works at -O0 and starts producing stale or reordered values at -O2, because the compiler reordered the accesses on the assumption that they could not interact. The failure has all the properties that make undefined behavior so unpleasant — no diagnostic, level-dependent, and the wrong value appears somewhere else.

The correct constructions are memcpy between the two objects, which every mainstream compiler recognises and compiles to nothing, or std::bit_cast in C++20. Union-based punning is well-defined in C and is not in C++, which is a difference worth remembering rather than deriving.

And -fno-strict-aliasing exists. It tells the compiler to assume any pointer may alias any other, which makes a great deal of legacy code correct at the cost of much of the optimization this lesson is about. The Linux kernel builds with it. That is a defensible engineering decision, and it is a decision, with a measurable price.

What this means when you are trying to make something fast

The practical consequence is that supplying aliasing information is often worth more than any transformation you could apply by hand. A restrict on two parameters can unlock hoisting, vectorization and load reuse simultaneously, and no amount of loop rewriting substitutes for it.

The second consequence is that pointer-heavy interfaces are pessimizing interfaces. A function taking a struct by pointer and reading its fields repeatedly must reload them after every store it cannot disambiguate; the same function taking the values by argument does not. Copying a small struct into locals at the top of a hot function is a real optimization for exactly this reason.

The third is that this is one of the strongest arguments for languages that answer the question in the type system. Rust's &mut is a checked restrict on every mutable reference in the program — the optimizer gets the answer for free, and the programmer cannot get it wrong without writing unsafe. That is what [[ownership-types]] buys at the optimizer level, in addition to what it buys at the safety level.

How it works

The steps, in the order the compiler takes them.

  • For each memory reference, identify its base object where possible: a named local, a parameter, a global, an allocation site, or unknown.
  • Two references to distinct non-escaping local objects cannot alias — the cheapest and most productive rule.
  • Two references at different constant offsets within the same object cannot alias; overlapping offsets must alias.
  • Apply the language's type-based rule where it has one: unrelated types do not overlap, subject to the standard's exceptions.
  • Apply programmer assertions: restrict parameters, noalias attributes, unique-reference guarantees from the frontend.
  • Where none of the above decides it, run a points-to analysis to compute the may-point-to sets, and answer no-alias when the sets are disjoint.
  • Combine the results of several analyses, taking the most precise definite answer, and return may-alias when nothing decides.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • A field is reloaded on every iteration of a loop that visibly never writes to it, and the loop is several times slower than it should be. Nothing is wrong; the compiler could not rule out an alias.
  • Code that computes correct answers at -O0 produces wrong ones at -O2, and the difference is a type-punning cast that violated strict aliasing. The wrong value appears in a computation several lines away from the cast.
  • A restrict-annotated function is called with overlapping arguments by a new caller, and the function silently computes something else. There is no diagnostic anywhere in the toolchain.
  • A loop refuses to vectorize and the diagnostic names a pair of pointers; adding restrict fixes it, and a later refactor removes the annotation and the regression returns unexplained.
  • A compiler upgrade improves alias analysis, a latent aliasing violation in old code is now exploited, and code that has "worked for years" breaks. The bug was always there.

When it helps

  • Any loop over arrays through pointers, which is most numerical and data-processing code — the single highest-value place to supply information.
  • Functions taking several pointer parameters of the same type, where the default assumption is maximally pessimistic.
  • Enabling other analyses: escape analysis, load/store elimination, vectorization and code motion are all consumers of the oracle rather than independent techniques.

When it hurts

  • Where the assertion is wrong. restrict is unchecked, and a violated restrict is undefined behavior with no symptom until it produces a wrong number.
  • Where relying on strict aliasing to optimize meets legacy code that violates it; the correct fix is often -fno-strict-aliasing for that code, at a real performance cost.
  • In precision-versus-compile-time terms: a fully interprocedural points-to analysis is expensive enough that compilers deliberately use a coarser one, so more precision is not free.

What it costs

Every one of these is paid by something.

  • A more precise analysis buys more optimization and costs compile time — Andersen-style points-to is roughly cubic, Steensgaard-style nearly linear and much coarser, and production compilers choose deliberately rather than always taking the precise one.
  • restrict buys the strongest possible answer at zero analysis cost and pays with an unchecked proof obligation whose violation is silent undefined behavior.
  • Strict aliasing buys type-based disambiguation for free across an entire program and costs the correctness of every program that reinterprets memory through incompatible pointer types — a trade the C committee made and that -fno-strict-aliasing exists to unmake.
  • A language-level guarantee such as Rust's &mut buys checked non-aliasing and costs the programmer the freedom to build data structures that require aliasing, which then need unsafe or interior mutability.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Copy the values into locals at the top of the function. The compiler knows a local's address does not escape, so all the aliasing questions disappear — crude, portable and frequently effective.
  • Pass by value rather than by pointer where the object is small; the aliasing question does not arise for a value.
  • Use memcpy or std::bit_cast for reinterpretation instead of a pointer cast — well-defined, and compiled to nothing by every mainstream compiler.
  • Use a language whose type system answers the question: Rust's uniqueness, Fortran's argument rules, or Swift's exclusivity all move the analysis from the optimizer to the frontend, where it can be checked.
  • Disable the assumption with -fno-strict-aliasing where legacy code depends on punning, and accept the code-quality cost knowingly.

See it for yourself

The flag, dump or tool that shows you this directly.

  • LLVM: opt -passes=aa-eval -aa-eval-print-all-alias-modref-info prints the oracle's answer for every pair of pointers in a function. It is the most direct look at this analysis available.
  • Check whether aliasing is the blocker empirically: add restrict and diff the assembly. If it changes, aliasing was the answer.
  • GCC: -fdump-tree-alias-details prints the points-to sets it computed; -Wstrict-aliasing=3 warns about some violations, and its incompleteness is itself instructive.
  • Clang: -Rpass-analysis=loop-vectorize names the specific pointer pair that blocked vectorization, which is usually the fastest route to the offending parameter.
  • For a suspected strict-aliasing bug: build with -fno-strict-aliasing and see if the bug disappears. If it does, there is a punning cast to find.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "The compiler reloads because it is not smart enough." It reloads because it is not *allowed* not to. Reordering across a possible alias would be a miscompilation.
  • "restrict is a hint." It is a promise. If it is false the program is undefined, and nothing checks it.
  • "Strict aliasing is a compiler optimization I can ignore." It is a language rule. Code that violates it is broken regardless of whether today's compiler exploits it.
  • "Casting a pointer and reading through it is fine because it works." It works until a compiler version, an optimization level or an inlining decision changes. That is the defining property of undefined behavior, not evidence of correctness.

Misconceptions

The claim, and what is actually true.

Aliasing only matters in C.
It matters everywhere there is mutable shared memory. Java and C# have it for array elements and object fields; the difference is that their type systems answer more of the questions, and none of them permits the punning cast that makes the C case dangerous.
restrict is a performance flag you sprinkle on pointers.
It is an unchecked correctness assertion. Applied wrongly it produces silent wrong answers, and the wrongness may only appear after an unrelated inlining decision changes.
Rust is faster than C because of the borrow checker.
Rust is not uniformly faster, but its uniqueness guarantee does give the optimizer aliasing information that a C compiler has to be told with restrict or must assume the worst about. That is a real, specific mechanism rather than a general claim.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

If two names might refer to the same piece of memory, the compiler has to assume they do, which means it cannot reuse a loaded value or move accesses around. Most of the time it cannot tell, so it assumes the worst, and that assumption is where a lot of missing optimization comes from.

practical

When memory-heavy code is slower than it looks like it should be, check for reloads in the disassembly before anything else. The fixes in order of value: copy the values into locals, add restrict, inline or expose the callee, and use a language guarantee if you have one. Never use restrict on pointers you cannot prove are distinct — the failure is silent.

advanced

The analysis is a whole-program constraint problem in its precise forms. Andersen's formulation treats assignments as subset constraints between points-to sets and solves them to a fixed point, giving inclusion-based precision at roughly cubic cost; Steensgaard's unifies the sets instead, giving near-linear time and much coarser results. Both are complicated by fields, arrays, function pointers, dynamic loading and, decisively, by concurrency: a sound analysis for multithreaded code must consider that another thread may write the location between any two accesses, which is why the memory model rather than the pointer analysis is what limits optimization around shared data — see [[semantics-drive-optimization]].

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

specStrict aliasing and the meaning of restrict are defined by the C and C++ standards, not by any compiler. GCC and Clang both enable strict-aliasing assumptions at -O2 and above and both offer -fno-strict-aliasing to disable them; a program that relies on punning through incompatible pointer types is undefined regardless of which one you use.
implementationLLVM combines several alias analyses — basic (address-based), TBAA, scoped-noalias, globals-modref — and answers with the most precise definite result. GCC has its own points-to machinery. Which analysis produced a given answer is visible only in the dumps, so attributing an optimization to "TBAA" from output alone is guesswork.
typicalMainstream compilers treat any call to a function whose body they cannot see as potentially writing to any memory reachable from its arguments and from globals. That single conservative rule blocks more memory optimization in ordinary code than the pointer analysis does, which is why inlining and LTO improve memory-heavy code so much.

If you were asked this in an interview

  • Why does a C function taking two int* parameters generate worse code than the same function taking two float* parameters?
  • What exactly does restrict promise, and what happens if the promise is false?
  • Explain a strict-aliasing bug: how it is written, why it works at -O0, and how you would fix it correctly.

Connections

Computer Architecturecache-linesmemory-hierarchyregisters
Concurrencymemory-modeldata-raceshappens-before
Performancememory-performancecpu-profiling
Securityinput-validation