Legalityspec

Optimization Legality

An optimization is valid only if it preserves the language's defined observable behavior. Every pass, every flag and every argument about undefined behavior in this domain is a consequence of that one sentence.

The question

What makes a transformation an optimization rather than a bug?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

IR, plus a set of facts some analysis has proved about it: which values are constants, which blocks dominate which others, which memory locations can be reached from where, which calls can be shown to have no effect. A transformation is never a rewrite of the IR alone — it is a rewrite guarded by a fact, and the representation that matters is the pair. The question the pair exists to answer is "am I allowed to do this to *this* program", which neither the instructions nor the analysis can answer alone.

What this phase may assume or do

A transformation is legal exactly when, for every input on which the original program has defined behavior, the transformed program produces the same observable behavior. Both halves carry weight. "For every input" rules out reasoning from the common case: a profile is evidence, never a proof, which is why a static compiler that wants to act on one must insert a guard. "On which the original program has defined behavior" is the escape hatch that C and C++ optimizers live inside: where the language defines nothing, no obligation exists, and the compiler owes that execution nothing at all.

Key points

An optimization is valid only if it preserves the language's defined observable behavior — for every input on which the original program was defined.
Every transformation is a fact plus an edit. The edit is the easy half; establishing the fact is what the middle-end's analyses exist for.
The language decides what is observable, before the compiler exists. The optimizer's job is to stay inside that decision, not to negotiate it.
Legal, profitable and enabled are three separate questions, and they fail in three different ways: a wrong program, a slow program, and a missed opportunity.
A profile is evidence, not a proof. Acting on one requires a guard and a fallback, which is what separates a JIT from a static compiler.
Where the language defines no behavior, the compiler has no obligation — which is why undefined behavior is an optimization topic and not only a safety topic.

One sentence, and everything hangs off it

Ask an engineer what an optimizer does and the answer is usually a list: it folds constants, it inlines, it unrolls loops, it removes dead code. That list is the surface. Underneath it there is a single rule, and every item on the list is a special case of applying it: a transformation may change anything about how the program runs, provided the behavior the language says is observable is unchanged.

Read the rule as a contract with two parties. The language specification says which effects of a program are part of its meaning. The compiler may then do absolutely anything else — reorder, merge, delete, duplicate, precompute, replace an algorithm with a different one — because none of it is part of the meaning. This is why "the compiler removed my benchmark loop" and "the compiler removed my memset" are not compiler bugs: the loop and the store were not observable under the rule the language wrote.

The important consequence is who decides. The optimizer does not get to choose what counts as observable, and neither does the person writing the pass. The *language* chose, before the compiler existed, and the compiler's job is to establish preconditions strong enough to be sure it stays inside them. That inversion — semantics decide, cleverness does not — is why this module sits between the transformations and the backend rather than at the end as a coda.

Legal — the rewrite preserves defined observable behavior on every input. This is a proof obligation, and it is binary.
Profitable — the rewrite makes the program better on some axis that matters. This is a heuristic, and it is frequently wrong.
Enabled — some earlier pass created the conditions under which the precondition can be established at all. This is [[phase-ordering]].
A pass that is legal and unprofitable is a waste of compile time. A pass that is profitable and illegal is a [[miscompilation]], and there is no amount of speed that redeems it.

A rewrite is a fact plus an edit

Every transformation in a real compiler has the same shape: establish a fact, then perform an edit that the fact makes safe. Writing the edit is the easy half and the half that gets attention; establishing the fact is where the analysis machinery of the entire middle-end lives, and where the bugs are.

The example below is deliberately unglamorous. Swapping a store and a load looks like nothing — no instruction is removed, nothing is precomputed, the program is the same length. It is still illegal without a fact, and the fact is expensive: the compiler must prove that the two memory operations cannot touch the same location. That proof is [[alias-analysis]], and the reason it is one of the hardest analyses in the middle-end is that almost every memory optimization is waiting on its answer.

Reordering a store past a load — no instruction removed, and still a proof obligation

Before

store @a, 1
%1 = load @b
%2 = int %1 + 1

After

%1 = load @b
store @a, 1
%2 = int %1 + 1

Legal only when

Only if @a and @b cannot name the same storage, neither access is declared volatile or atomic, and no other thread or signal handler may observe the interleaving of the two. Under those conditions the memory traffic is unobservable in either order, so the order is the compiler's to choose — and choosing it is what lets the load issue earlier and cover its own latency.

Illegal when

@a and @b may alias — two pointers derived from the same allocation, a union, a pointer passed in by a caller who kept another copy. Then the load reads the value the store just wrote in one order and the previous value in the other, and the program computes a different number. The same rewrite is also illegal if either location is volatile, because a volatile access is observable behavior in its own right, or if a concurrent reader can see the two writes in either order — the memory model in Concurrency is what decides that case, and it is linked below.

Our pass manager states its preconditions out loud

simplifiedAtlasLang has no pointers, no threads, no exceptions, no floating point and no foreign functions, which is the only reason these preconditions fit in a sentence each. In LLVM the equivalent facts are a lattice of per-function and per-call-site memory-effect attributes, an alias-analysis pipeline with several cooperating implementations, and an analysis manager that tracks which facts a transformation invalidated. The *shape* of the argument is identical in both; the cost of establishing the facts is not remotely comparable.

The AtlasLang optimizer at /compilers/passes was built to make this visible rather than to be fast. Each of its eight passes carries two strings in the source next to its implementation: the precondition that makes it valid, and a concrete program where the same rewrite would be wrong. Toggling a pass shows both, alongside the IR before and after that pass ran.

The page also runs the program twice — once from the unoptimized IR and once from the optimized IR — and asserts that the two produce identical output. That assertion is the lesson made executable. It is not a proof of anything; it is a single test on a single input, and a real compiler needs thousands of them plus [[differential-testing]] plus [[compiler-fuzzing]]. What it does demonstrate is the discipline: a transformation that changes what the program prints has failed, no matter how much smaller the instruction count became.

Two of the preconditions in that table do all the work, and both are functions you can read. hasEffect decides whether an instruction may ever be deleted; it returns true for print, store, param and every call, because AtlasLang has no way to express purity and assuming it without proof is the specific bug the predicate exists to prevent. mayTrap decides whether an instruction may be evaluated early; it returns true for a division whose divisor is not a provably non-zero literal, which is why 10 / 0 survives folding and faults at run time where the language said it would.

The eight AtlasLang passes and the fact each one must establish firstsimplified

Pass	The precondition	Where the same edit would be wrong
Constant folding	Both operands are literals and the operation cannot trap.	`1 / 0` — folding moves a run-time fault into the build.
Strength reduction	The rewritten form gives the identical value for every input the operand type admits.	`x + 0.0` on floats, which turns negative zero into positive zero.
Constant propagation	The value has exactly one definition and that definition is a literal.	Outside SSA, where a second definition on another path also reaches the use.
Copy propagation	The definition is a pure copy of a value that is unmodified at every use.	Non-SSA code where the source is reassigned between the copy and the use.
Branch simplification	The condition folded to a literal, so one edge is provably never taken.	The condition is merely usually true — that needs a guard and a deoptimization path.
Unreachable block elimination	No path from the entry reaches the block.	The block is reachable through an edge the analysis did not model: an exception, a computed jump.
Common subexpression elimination	The same pure operation on the same operands, with the first dominating the second.	Memory was written between the two, so the operands are no longer the same values.
Dead code elimination	No side effect and no remaining user. Both halves.	A call whose result is unused but which prints, locks or writes a file.

Legal is not the same as profitable, and neither is a guess

A compiler that only asked "is this legal" would inline every call, unroll every loop and specialize every generic, and produce a binary too large to fit in an instruction cache. Legality is a gate, not a goal. Behind it sits a second question — is this rewrite worth it — that is answered by heuristics, cost models and budgets, and those are guesses about a machine the compiler cannot observe.

The two questions fail in completely different ways, and telling them apart is most of what makes compiler output legible. A legality failure is a wrong program: silently wrong output, a deleted security-critical store, a check that no longer runs. A profitability failure is a correct program that is slower or larger than it should be: an inlining decision that blew out instruction-cache pressure, an unrolled loop nobody executes twice, a vectorized body with more setup than work. The first is a bug report; the second is a tuning problem, and the only way to settle it is measurement.

There is a third category worth naming because it is where JIT compilers live. A speculative transformation is one that is *not* legal in general but is made legal by a guard: check at run time that the assumption still holds, and if it does not, fall back to code that does not assume it. That converts an unprovable fact into a cheap run-time test, which is the entire trick behind [[speculative-optimization]] and [[inline-caches]], and it is why a JIT can perform rewrites a static compiler must refuse.

How it works

The steps, in the order the compiler takes them.

A pass asks an analysis for the facts it needs: constant values, dominance, liveness, aliasing, effects.
It tests its precondition against those facts for the specific instruction or region it is considering.
If the precondition holds, it performs the edit and records that it changed something.
If the precondition cannot be established, it declines — conservatively, because "I could not prove it" and "it is false" must lead to the same decision.
Analyses that the edit invalidated are discarded or recomputed, because acting on a stale fact is indistinguishable from having no precondition at all.
The pass manager repeats the pipeline while anything is still changing, since each edit can make another pass's precondition provable.
A verifier re-checks the IR's structural invariants after the run, catching the class of bug where an edit left the representation malformed rather than merely wrong — [[ir-verification]].

How it breaks

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

A release build produces a different answer from a debug build, on one input in ten thousand, because a pass applied a rewrite whose precondition it had not actually established.
A security-critical store that zeroes a key buffer is gone from the disassembly, and the key stays in memory across the rest of the process's life.
A benchmark reports an implausible number because the loop it measured was removed entirely — the work was legal to delete, and the measurement was therefore of nothing.
A program works at -O0 and crashes at -O2, and the crash is in a function far from the one that contains the actual mistake, because the transformation that exposed it moved the consequence.
A guard-free speculative rewrite in a JIT is right for the first ten thousand calls and wrong for the ten-thousand-and-first, when a subclass arrives that the inline cache never saw.

When it helps

Reading compiler output: knowing that every removal required a proof turns "why did it do that" into "what did it believe", which is answerable from the dump flags.
Filing compiler bugs. A report that names the transformation and the precondition it violated is actionable; "the optimizer broke my code" is not.
Reviewing a compiler pass, where the only question that matters is which analysis supplies the fact and what happens when the analysis cannot decide.
Deciding what to write in the source: an effect the compiler is entitled to remove has to be made observable — volatile, an atomic, an opaque call, an explicit barrier.

When it hurts

Treating legality as a promise of quality. A compiler can be perfectly legal and useless, and most of the interesting engineering is in the heuristics on the other side of the gate.
Assuming the rule is enforced. Nothing in a compiler checks that a pass established its precondition; the preconditions live in comments, in reviewers' heads, and in test suites, which is why [[translation-validation]] and [[verified-compilers]] exist.

What it costs

Every one of these is paid by something.

Insisting on proof rather than likelihood buys correctness and pays real optimization: every fact the analysis cannot establish becomes a rewrite that does not happen, and conservative answers are the single largest source of missed optimization in practice.
Stronger analyses buy more provable facts and pay compile time and implementation surface — a precise interprocedural alias analysis can cost more than every transformation it enables, which is why production compilers run a cheap one first and a precise one only where it might matter.
Speculating with guards buys transformations that are not statically provable and pays run-time checks, code for the fallback path, and the memory to keep the unoptimized version alive — see [[deoptimization]].
Making the preconditions explicit in the source, as the AtlasLang passes do, buys reviewability and pays verbosity; most production compilers state them in comments and design documents instead, which is cheaper and ages worse.

What else you could do

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

Verify the transformation instead of trusting it: CompCert proves each pass preserves semantics in Coq, so legality is a theorem rather than a convention — at the cost of years of proof effort and a much smaller set of optimizations — [[verified-compilers]].
Check the result instead of the pass: translation validation compares the input and output of each run and reports a mismatch, catching bugs in an unverified optimizer without proving the optimizer correct — [[translation-validation]].
Move the guarantee into the language: a language with no undefined behavior and an effect system gives the compiler far fewer assumptions to make and far more facts to read off the types, which is the Rust and Haskell direction — [[effect-systems]].
Give up on proving and speculate with a fallback, which is what every serious JIT does and what a static compiler for a language without deoptimization support cannot.

See it for yourself

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

Toggle passes individually at /compilers/passes and read the precondition each one prints; the page also runs the unoptimized and optimized IR and compares their output.
LLVM: opt -passes=... -print-changed prints the IR after every pass that modified it, so a removal can be attributed to a specific transformation rather than guessed at.
LLVM: -Rpass=inline, -Rpass-missed=inline and -Rpass-analysis=inline report what was transformed, what was not, and why the analysis declined — the "why not" remarks are the most useful compiler output most engineers have never enabled.
GCC: -fopt-info-missed and -fopt-info-vec-missed print the transformations that were considered and rejected, usually with the unestablished precondition named.
Compare -O0 and -O2 output for the same source in Compiler Explorer, then reintroduce the thing you expected to survive as a volatile access and diff again — the difference is exactly what the compiler considered unobservable.

Plausible wrong readings

Stated the way a confident engineer states them.

"The compiler optimizes my code." It rewrites your code under constraints you did not write down and it did not choose. Most of what it does not do, it declines to do because it could not prove something.
"If the optimizer removed it, it was useless." It was unobservable *under the model the language permits*. Hardware registers, other threads, secret material and elapsed time are all observers that model does not include unless you say so.
"An optimization is safe if the tests pass." Legality is a claim about every input. A pass whose precondition is wrong is wrong on the inputs nobody tested, which is where miscompilations are found — usually years later.
"Faster is the goal, so anything that makes it faster is an improvement." Anything that changes defined observable behavior is a wrong program, and a wrong program has no speed worth discussing.

Misconceptions

The claim, and what is actually true.

The optimizer is allowed to do anything that makes the program faster.

It is allowed to do anything that leaves defined observable behavior unchanged. Speed is not part of the test, and plenty of legal transformations make code slower.

Optimization legality is about avoiding compiler bugs.

It is about what the language permits, which is a design decision made long before any compiler. A language with more defined behavior gets a less aggressive compiler, and that is a trade the language made deliberately.

If a transformation is legal it will be applied.

Legality is one gate. A cost model, a budget and the current pass order all sit behind it, and most legal transformations in any given function are declined for being unprofitable or never even considered.

Go deeper

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

overview

A compiler may rearrange your program however it likes as long as what the program is defined to *do* stays the same. Printing, writing files and other visible effects have to survive. How long it takes, how much memory it uses and which instructions run are not part of the deal, so the compiler is free to change all of them.

practical

When code disappears or behaves differently at a higher optimization level, do not start from "compiler bug". Start from "what was the compiler entitled to assume". Usually the answer is that the effect you cared about was not observable under the language's rules — a store nobody reads, a loop with no visible effect, an overflow the language left undefined. The fix is to make it observable rather than to lower the optimization level, because lowering the level hides the problem on one build and not another.

advanced

The deep tension is that the strength of an optimizer is bounded by the weakness of the language's guarantees, and every guarantee a language adds is an optimization it takes away. Java's memory model forbids reorderings C permits; Rust's defined overflow forbids inferences C makes routinely; a language with no undefined behavior at all must check what C assumes. That is the real content of the "safe languages are slower" argument, and it is quantitative rather than categorical — the checks a safe language inserts are frequently removable by an analysis that a language with more guarantees is better placed to run. AtlasLang sits at the extreme: no undefined behavior at all, everything checked, and an optimizer whose preconditions are correspondingly simple to state and correspondingly weak.

How much this depends on

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

specThe formulation "same observable behavior for inputs on which the original is defined" is the C and C++ as-if rule, and languages differ on both halves. Java specifies a memory model that constrains reordering even in the absence of data races and has no undefined behavior to exploit; Rust defines integer overflow in both build profiles; Python's language reference leaves far more to the implementation than either. Carrying C's formulation to another language is the standard way to be confidently wrong about what its compiler may do.

implementationThat preconditions are written in the pass source is true of the AtlasLang optimizer in this build and is a teaching choice. LLVM and GCC record theirs in comments, in the LangRef's semantics for each instruction and attribute, and in the analyses themselves; there is no single place a reader can go to enumerate them, which is part of why the rule is so often stated as folklore.

typicalMainstream compilers decline a transformation when an analysis returns "unknown", treating it identically to "false". That conservatism is what makes them sound, and it is also why adding one attribute — restrict, noalias, const — can unlock a large amount of previously blocked optimization: it supplies a fact the compiler could not derive.

If you were asked this in an interview

What has to be true before a compiler may delete an instruction?
A colleague says the optimizer broke their code. What do you ask them first?
Why can a JIT perform transformations a static compiler must refuse, given both are compiling the same language?

Connections

Computer Architectureinstruction-cache

Concurrencymemory-model data-races

Performancemeasure-before-optimizing benchmark-fallacies

Domains that do not exist yet

Testing & Reliability Engineering — Metamorphic and differential testing as general techniques
Nothing inside a compiler checks that a pass established its precondition, so the practical defence is testing the same program under different transformation settings and comparing. The techniques are owned there; the compiler-specific applications are [[differential-testing]] and [[compiler-fuzzing]].