Legalityspec

Semantics Decide, Not Cleverness

Can integer overflow occur? Can two references alias? Can a function have hidden side effects? The answers are properties of the language, and they decide what its compiler may do — which is why the same transformation is routine in C, forbidden in Java and unnecessary in Rust.

The question

Why does the same optimization happen in one language and not another, for identical-looking source?

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

A typed IR plus the *guarantees the source language attached to it*: whether arithmetic may wrap, whether two references may denote the same storage, whether a call may do something the caller cannot see, whether a field may be null. Two frontends can emit structurally identical IR and hand the middle-end completely different sets of these guarantees, and the middle-end will then generate different code from the same instructions. The representation exists to answer "what may I assume about this program", and its answer comes from the frontend, not from analysis.

What this phase may assume or do

A middle-end may only use the guarantees its frontend actually attached. The precondition for every language-derived optimization is the same: the source language must define the property in a way that makes the assumption sound for every program it accepts. noalias on a Rust &mut is sound because the borrow checker proved uniqueness; the same attribute on a C pointer is sound only when the programmer wrote restrict and was telling the truth, which is why the two carry the same IR flag with completely different confidence behind it.

Key points

  • Three questions decide most of the difference between languages: can arithmetic overflow, can references alias, can a call have hidden effects.
  • The answers are properties of the language, fixed before any compiler exists, and they bound what any implementation of it may do.
  • C obtains aliasing freedom by assertion (restrict, strict aliasing) with no diagnostic when the assertion is false; Rust obtains it by construction, checked.
  • Both end up as the same LLVM noalias attribute — identical IR, completely different confidence behind it.
  • An unanalysable call is a barrier: it blocks removal, reordering and register caching around it, which is why purity annotations and effect systems unlock so much.
  • Cleverness moves what can be proved; the language decides what may be assumed, and the second is much cheaper than the first.
  • A dynamic language recovers assumptions at run time with guards and deoptimization instead of getting them from the specification.

Three questions that decide most of it

specThese are language-level guarantees, not compiler behaviors, and the Rust column deliberately describes both build profiles because they differ in a way the standard C column has no analogue for: overflow panics under debug-assertions and wraps otherwise, and both are defined, so a Rust program's meaning is profile-dependent by design rather than by accident. The Python column describes the language reference rather than CPython, since CPython, PyPy and a restricted-semantics compiler like Mypyc make very different assumptions about the last row.

A middle-end asks a small number of questions over and over, and the answers are fixed by the source language long before any pass runs. Three of them account for most of the difference between what one language's compiler can do and another's.

Can arithmetic overflow, and what happens if it does? If overflow is undefined, the compiler may treat arithmetic as monotone: loop counters do not wrap, x + 1 > x is true, a 32-bit induction variable may be widened to a register without a check. If overflow is defined to wrap, all of those inferences are unavailable and the wrap must be reproduced exactly. If it traps or panics, the operation is no longer even removable, because the trap is observable.

Can two references denote the same storage? If they can, a store through one may invalidate a value loaded through the other, and almost every memory optimization — keeping a value in a register across a store, reordering loads and stores, vectorizing a loop over two arrays — becomes blocked pending an alias analysis. If the language guarantees they cannot, the optimizations are unlocked without any analysis at all. This is the single largest structural difference between C and Rust in the middle-end.

Can a call do something the caller cannot see? If any call may perform I/O, write arbitrary memory, take a lock or not return, then a call is a barrier: nothing crosses it, nothing around it can be removed, and every value that might be reachable from it must be written back to memory first. If purity is expressible and checked, calls become ordinary expressions that can be folded, hoisted, deduplicated and deleted.

Notice what is *not* on this list: how good the compiler is. A very sophisticated C compiler cannot assume &mut-style uniqueness, and a modest Rust compiler gets it for free. Cleverness moves the boundary of what can be *proved*; the language decides what may be *assumed*.

The same questions, four languagesspec
QuestionCRustJavaPython
Signed integer overflowUndefined — may be assumed impossiblePanics in debug, wraps in release; both definedDefined to wrap, two's complementNo fixed width; integers grow
Unsigned integer overflowDefined to wrapSame as signed: panic or wrap by profileNo unsigned integer types (except char)Not applicable
May two references alias?Yes, unless restrict is asserted by handA &mut is unique by construction, checkedYes — any two references of compatible typeYes — everything is a reference
May unrelated types overlap?No, by the strict-aliasing rule — an assumptionNo, enforced by the type systemNo, enforced by the runtimeNot a meaningful question
Can a call have hidden effects?Yes, unless annotated pure/constYes, but ownership bounds what it can reachYes; the JIT infers purity from bytecode it can seeYes, including rebinding names in the caller's module
Can a field be null?Yes, and dereferencing null is undefinedOnly if the type is Option<T>Yes, and dereferencing throwsYes — None is an ordinary value
Are array accesses checked?No; out of bounds is undefinedYes, and the check is often eliminated by analysisYes, and it throwsYes, and negative indices are defined
Can a name be rebound at run time?NoNoClasses may be loaded, so a call site may gain targetsYes — any global, method or module attribute

What each guarantee is worth in emitted code

The aliasing row is the one with the largest practical consequence, and it is worth seeing concretely. Consider a function taking two pointers to arrays and adding one into the other. In C, the compiler must assume the two may overlap, so each store may invalidate the next load, and the loop cannot be vectorized without a run-time overlap check — which mainstream compilers do insert, splitting the loop into a vectorized version and a scalar fallback, and paying code size for both.

Marking the parameters restrict supplies the guarantee by assertion and the check disappears; getting it wrong is undefined behavior with no diagnostic. In Rust, &mut [f32] carries the same guarantee by construction, checked by the borrow checker, and rustc emits noalias on the parameter — the same LLVM attribute, with a proof behind it instead of a promise. In Java, the arrays are references that may alias and the language provides no way to say otherwise, so the JIT relies on run-time checks and profile information instead.

The purity row plays out similarly. In C, an unannotated call to another translation unit blocks everything around it; adding __attribute__((const)) unlocks folding, hoisting and deduplication of the call, and lying about it is undefined. In Haskell, purity is the default and is checked by the type system, so the compiler can float, duplicate and delete calls freely — and the interesting consequence is the reverse one: because everything is pure, GHC has to work hard to make effects *happen* in a specified order, which is what the IO type is for.

The same loop, and whether it needs an overlap check
Before
void add(float *a, float *b, int n) {
  for (int i = 0; i < n; i++)
    a[i] += b[i];
}
After
void add(float *restrict a, float *restrict b, int n) {
  for (int i = 0; i < n; i++)
    a[i] += b[i];   /* vectorized with no run-time overlap check */
}
Legal only when

Vectorizing without a check is legal only if the objects a and b point into do not overlap for the duration of the call. restrict is the programmer asserting exactly that, and the compiler is then entitled to assume it. Rust obtains the same guarantee from &mut [f32] without any assertion, because uniqueness is a checked property of the type — which is why the equivalent Rust function vectorizes without the programmer doing anything.

Illegal when

The pointers do overlap and restrict was written anyway — undefined behavior, no diagnostic, and a wrong result only for the overlapping inputs, which are exactly the ones nobody tests. It is also illegal without the annotation to skip the check entirely: without a guarantee, mainstream compilers emit a run-time overlap test and two loop bodies, paying code size to keep the vectorized version available. See [[alias-analysis]] and [[compiler-vectorization]].

Reading this as a language designer, and as a user

For a language designer, every guarantee is a two-sided trade and the sides are not symmetric. Defining a behavior costs an optimization and buys predictability. Leaving it undefined buys an optimization and costs a class of bug with no diagnostic. Making it *unrepresentable* — Rust's answer for aliasing and null — costs expressiveness and a learning curve, and buys both the optimization and the predictability. The third option is the most expensive to design and the cheapest to live with, which is roughly the story of the last twenty years of language design.

For a user, the conclusion is more immediate: performance advice does not port. "The compiler will hoist that out of the loop" depends on whether a call in the loop body might have effects, which depends on the language. "Use an array of structs" depends on layout guarantees. "This branch is free" depends on whether the language permits speculating past it. Carrying a performance intuition from C to Java or from Java to Python is how teams end up optimizing something that was never the cost.

It also reframes what a fast implementation of a dynamic language must do. CPython cannot assume much of anything: a name may be rebound, a method may be replaced, an integer may grow without bound. A JIT recovers the assumptions at run time by observing what actually happened and guarding on it — which is exactly [[speculative-optimization]], and why [[guards]] and [[deoptimization]] are the load-bearing machinery rather than the clever part. The static compiler asks the language; the JIT asks the execution.

How it works

The steps, in the order the compiler takes them.

  • The frontend translates source to IR and attaches the guarantees its language provides: overflow flags, alias attributes, effect attributes, nullability.
  • Where the language obtains a guarantee by checking — Rust's borrow checker, a type system that excludes null — the frontend attaches it unconditionally.
  • Where the language obtains it by assertion — restrict, __attribute__((const)) — the frontend attaches it on the programmer's word, with undefined behavior as the penalty for lying.
  • Where no guarantee exists, the middle-end must derive it with an analysis, or decline the transformation.
  • Analyses combine language-supplied facts with derived ones; passes cannot tell the two apart, which is why one attribute can change generated code dramatically.
  • For languages that supply almost nothing, a JIT observes actual behavior, installs a guard encoding the observation, and optimizes under it — with a deoptimization path for when the guard fails.

How it breaks

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

  • A hot loop that vectorized in a Rust port refuses to vectorize in the C original, and the team concludes the C compiler is worse rather than that it lacks a guarantee.
  • restrict is added to silence a missed-optimization report on pointers that do sometimes overlap, and a wrong result appears only for inputs where they do.
  • A performance recipe carried from C to Java produces no improvement, because the transformation it relied on was never legal there.
  • A Python micro-optimization is defeated because a module-level name can be rebound, so the interpreter must look it up every time — and the developer attributes the cost to the loop.
  • A team adds __attribute__((pure)) to a function that caches internally, and calls are deduplicated across a state change, producing a stale value with no crash.
  • A JIT-optimized method silently deoptimizes when a new class is loaded, and a benchmark that was stable for an hour regresses after a deployment adds a subclass.

When it helps

  • Comparing compilers or languages honestly: the first question is which guarantees each one has, not which optimizer is better.
  • Porting performance-sensitive code, where knowing which assumptions you are losing predicts where the regressions will be.
  • Deciding whether an annotation is worth it: restrict and purity attributes are cheap to add and are undefined behavior when wrong, which is exactly the trade to make consciously.
  • Designing a DSL or an internal language, where the guarantees you build in decide how much analysis you will have to write later — [[dsl-implementation-strategies]].

When it hurts

  • As an argument that one language is simply faster. The guarantees differ, and so do the workloads that care; the comparison is only meaningful for a specific program, measured.
  • When it becomes a reason to annotate everything. Each assertion-based guarantee is an undefined-behavior obligation with no diagnostic, and restrict on pointers that overlap is a genuinely nasty bug to find.

What it costs

Every one of these is paid by something.

  • Guaranteeing more buys optimization without analysis and pays expressiveness: Rust's uniqueness guarantee forbids programs that are perfectly correct, which is the cost of getting noalias for free.
  • Leaving more undefined buys the same optimizations at zero language-design cost and pays with bugs that have no diagnostic and a symptom far from the cause.
  • Obtaining guarantees by assertion buys a migration path for an existing language and pays the entire proof obligation to the programmer, silently.
  • Recovering guarantees at run time with a JIT buys optimization for languages that promise nothing and pays warmup, memory for the unoptimized versions, and the complexity of deoptimization — [[jit-costs]].

What else you could do

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

  • Effect systems make purity a checked part of the type rather than an annotation or an inference, so the compiler can move and delete calls soundly — Haskell and Koka — [[effect-systems]].
  • Ownership and lifetimes make aliasing a checked property rather than an assertion, which is the Rust answer and the reason its middle-end gets attributes a C frontend cannot emit — [[ownership-types]].
  • Whole-program analysis recovers some guarantees the language did not give: if the compiler can see every call site, it can prove purity, devirtualize and specialize — [[whole-program-optimization]].
  • Profile-guided compilation substitutes measured behavior for guarantees, which is weaker but applies to languages that guarantee nothing — [[profile-guided-optimization]].

See it for yourself

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

  • Compile the add loop above in C with and without restrict at -O2 and diff: without it you will find a run-time overlap check and two loop bodies.
  • Compile the equivalent Rust function and read the LLVM IR with cargo rustc -- --emit=llvm-ir: the noalias attribute is on the parameters, emitted by the frontend rather than derived.
  • clang -Rpass-missed=loop-vectorize reports why a loop was not vectorized, and "cannot prove pointers do not alias" is the most common answer.
  • Java: run with -XX:+UnlockDiagnosticVMOptions -XX:+PrintInlining and observe how much of the JIT's work is recovering facts a static language would have been given.
  • Python: dis.dis a function with a global call and note the LOAD_GLOBAL on every iteration — the cost of a name that may be rebound, visible in the bytecode.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Language X has a better optimizer." Sometimes. More often it has better guarantees, and the optimizer is the same LLVM in both cases.
  • "Rust is fast because it has no garbage collector." That is one reason among several; the aliasing guarantee it hands the middle-end is a distinct and separately valuable one.
  • "If I write the same algorithm, I get the same code." The same algorithm in two languages hands the middle-end different premises, and the emitted code differs accordingly.
  • "Annotations are just hints." restrict and __attribute__((const)) are not hints. They are assertions whose falsity is undefined behavior, and the compiler will act on them without checking.

Misconceptions

The claim, and what is actually true.

Optimization is mostly about how good the compiler is.
It is mostly about what the language lets the compiler assume. The same LLVM backend produces different code for C and Rust frontends because the frontends hand it different guarantees.
Safety features cost performance.
Some do and some pay for themselves. Bounds checks cost until an analysis removes them; the uniqueness guarantee that comes with Rust's borrow checker is a net gain in the middle-end.
A dynamic language cannot be optimized.
It cannot be optimized from assumptions, so it is optimized from observations instead — guarded speculation, with a deoptimization path. That is a different technique with different costs, not an absence of technique.

Go deeper

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

overview

Compilers differ less than the languages they compile. Whether numbers can overflow, whether two references can point at the same thing, and whether a function can secretly do something are decided by the language, and those answers decide what any compiler for it may do. That is why the same code can be optimized aggressively in one language and barely touched in another.

practical

Do not carry performance advice across languages. When a loop is slow, ask which guarantee is missing rather than which flag is wrong: usually it is aliasing or an opaque call. In C you can supply the missing guarantee with restrict or a purity attribute — but only if it is actually true, because a false assertion is undefined behavior with no diagnostic. In Rust the same guarantees come from the types. In Java and Python they mostly do not come at all, and the runtime recovers them by watching what your program actually does.

advanced

The design frontier here is guarantees that are cheap to check and valuable to assume. Aliasing is the great example: for thirty years C tried to get it by assertion and by type-based rules, both of which are unsound in practice, and Rust obtained it by making uniqueness a checked property of a reference type. The same move is being attempted for effects, where the tension is that a fully checked effect system changes every function signature in the language, and for nullability, where retrofitting it onto an existing language produces the gradual, partially-checked systems seen in Kotlin, C# and TypeScript. In each case the compiler-facing question is identical: is this guarantee strong enough to attach to the IR unconditionally, or does it need a fallback path for the cases the checker could not decide?

How much this depends on

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

specEvery cell in the comparison table is a language-level statement, taken from the C and C++ standards, the Rust reference, the Java Language Specification and the Python language reference. Implementations may be more conservative than their specification permits — MSVC has historically exploited strict aliasing less than GCC — but none may be more aggressive, which is what makes the specification the right level to reason at.
implementationThat rustc emits noalias on &mut parameters is true of current rustc on LLVM, and it was disabled for several releases in the past because of LLVM bugs that the attribute exposed. This is a good illustration of the general point: the guarantee is a property of the language, but whether a given release exploits it is a property of the implementation and its bug history.
typicalMainstream C compilers respond to an unprovable aliasing question by emitting a run-time check and two versions of the loop rather than by giving up, so the cost of a missing guarantee shows up as code size and a branch rather than as unvectorized code. Whether that versioning happens depends on the loop's estimated profitability, so small loops simply stay scalar.

If you were asked this in an interview

  • Why does the same loop vectorize in Rust and not in C without annotations?
  • What does an unanalysable function call cost the optimizer around it, and why?
  • A dynamic language guarantees almost nothing. How does a JIT get optimization out of it anyway?

Connections

Computer Architecturesimdcache-lines
Concurrencymemory-modeldata-races
Performancemeasure-before-optimizingbenchmark-fallacies
Domains that do not exist yet
  • Programming Languages & Runtime Internals — Object representation and dynamic dispatch at run time
    The last row of the comparison — whether a name can be rebound — is a runtime representation question, and it decides whether a call site can be resolved statically at all. The compiler-side half is devirtualization and inline caches; the runtime-side half, including how a method table is updated when a class is loaded, is owned there.