AtlasLangimplementation

AtlasLang: Eight Passes and Two Guards

Eight transformations over SSA, run to a fixed point, each carrying its legality precondition as data rather than as a comment. Two predicates do all the safety work: a `print` is never removed, and `x / 0` is never folded.

The question

Which optimizations does AtlasLang actually perform, and what stops each one from being a bug?

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

What the program is here

SSA over a control-flow graph: every value defined exactly once, phi nodes at merges, blocks linked by explicit predecessor and successor edges. That single-definition property is what most of these passes are built on — "the definition of this value" is a lookup rather than an analysis, which is what makes constant and copy propagation two-line passes here and multi-page ones on ordinary three-address code.

What this phase may assume or do

Every pass rewrites the program, so every pass carries a precondition, and in this implementation the precondition is a field rather than a comment: PASSES in src/compilers/sim/optimize.ts is an array of objects with legal and illegalWhen populated for each. Two predicates cover the cases where the preconditions bite. hasEffect(i) reports whether an instruction can be observed other than through the value it produces — print, store, call and param all can — so nothing effectful is ever deleted however dead its result. mayTrap(i) reports whether evaluating an instruction can fault, which for AtlasLang means integer division or remainder by a divisor the compiler cannot prove non-zero, so 10 / 0 is never folded at build time.

Key points

Eight passes — folding, strength reduction, constant propagation, copy propagation, branch simplification, unreachable-block elimination, CSE, DCE — run to a fixed point.
Every pass carries legal and illegalWhen as data in PASSES, so a rewrite cannot be shown without the condition that makes it valid.
hasEffect is why a print with no reader survives: an instruction may be deleted only if nothing outside its value can observe that it ran.
mayTrap is why 10 / 0 is not folded: folding would move a runtime fault to build time, which is a different observable behavior.
mayTrap is precise, not blanket — 10 / 2 folds, because a literal non-zero divisor is provably safe.
Three passes are cheap only because the input is SSA: single definition makes propagation a lookup, and dominance makes CSE's availability condition free.
The fixed point matters because passes enable each other: folding to propagation to branch simplification to unreachable blocks to dead definitions.
The iteration cap of twelve is a termination guard against a future oscillating pass, not a tuning parameter.

The eight passes

Each is short, each is real, and each states the condition under which its rewrite preserves behavior along with a program where the same rewrite would be wrong. The illegalWhen column is the one worth reading, because it is where the reasoning is.

Notice that three of the eight are only cheap because the input is SSA. Constant propagation needs to know that a value has exactly one definition — guaranteed by construction. Copy propagation needs the source of a copy to be unmodified between the copy and the use — also guaranteed, because nothing is ever modified. Common subexpression elimination needs the earlier computation to be available on every path reaching the later one, which is exactly what dominance establishes. Outside SSA, each of those requires a data-flow analysis to justify.

PASSES from src/compilers/sim/optimize.tsimplementation

Pass	Legal when	Would be wrong when
Constant folding	Both operands are literals and the operation cannot trap.	`1 / 0` — folding moves a runtime fault to build time. Or the result depends on runtime state such as a rounding mode.
Strength reduction	The rewritten form yields an identical value for every input the operand types admit.	`x + 0.0` is not `x` in IEEE-754 — it turns negative zero positive. AtlasLang has no floats, which is the only reason the identity is unconditional here.
Constant propagation	The value has exactly one definition and it is a literal — guaranteed by SSA.	Outside SSA, two definitions reach the same use and a reaching-definitions analysis is needed to rule it out.
Copy propagation	The definition is a pure copy of a value that is unmodified at every use — again free in SSA.	The source is reassigned between the copy and the use, which is the classic non-SSA hazard.
Branch simplification	The condition folded to a literal, so the untaken edge can never execute.	The condition merely usually has that value. A profile is evidence, not proof — acting on it needs a guard and a deoptimization path.
Unreachable block elimination	No path from entry reaches the block, so nothing in it is observable.	The block is reachable through an edge the analysis did not model — an exception edge, a computed jump, an escaped label. AtlasLang has none.
Common subexpression elimination	Two pure instructions compute the same operation on the same operands, and the first dominates the second.	The operation reads memory that may have been written between them, which needs alias analysis — why CSE over memory is far harder than over registers.
Dead code elimination	The instruction has no side effect and nothing uses its result.	The instruction prints, calls, writes memory or can trap. Removing an effectful instruction because its value is unused is a miscompilation.

The two guards, demonstrated

The difference between an optimizer and a bug is entirely in these two predicates, and both have a dedicated example program so you can watch them refuse.

`hasEffect` — a print is never removed. Load the effect example: let unused = 1 + 1; print(42);. The binding is folded, propagated and then deleted, because nothing reads it. print(42) remains, and it remains even though nothing reads *its* result either — because it does not have a result, it has an effect. An optimizer that reasons only about value use deletes it. In AtlasLang, print, store, call and param are all effectful; call in particular is assumed effectful unconditionally, because the language has no purity annotation and assuming purity without proof is exactly the miscompilation the predicate exists to prevent.

`mayTrap` — `x / 0` is never folded. Load the trap example: let a = 10; let b = 0; print(a / b);. Constant propagation happily replaces both operands, producing %2 = int 10 / 0. Then constant folding declines. The reasoning is not that the program is fine — it is not; it faults. The reasoning is that folding would move that fault from run time to build time, which changes what the program does: a build that fails is not the same behavior as a program that runs and faults, and a compiler that refuses to compile a program because one of its paths would divide by zero is refusing programs where that path is never taken.

The predicate is precise rather than blanket. A literal non-zero divisor *is* provably safe, so 10 / 2 folds to 5. Only a divisor the compiler cannot prove non-zero blocks the fold. That precision is the difference between a legality condition and a superstition.

Two refusals, from the real optimizer

The `trap` example — after propagation

fn main(): void {
b0: ; entry
  %2 = int 10 / 0
  print %2
  ret
}

The `effect` example — fully optimized

▸fn main(): void {
▸b0: ; entry
▸  print 42
▸  ret
▸}

Read it asOn the left, both constants were propagated into the division and then the fold stopped — mayTrap returned true, so the instruction survives and the VM faults at run time with the message "Division by zero. This is a real fault, which is why the optimizer refuses to fold x / 0 at compile time." On the right, 1 + 1 was folded, propagated and deleted, while print 42 survives with no reader — hasEffect returned true. Two refusals, two different reasons, both in the code rather than in the prose.

Running to a fixed point

implementationEight passes to a fixed point with a cap of twelve iterations is AtlasLang's pipeline at this revision. LLVM at -O2 runs on the order of a hundred and fifty pass instances in a fixed, hand-tuned order with an explicit inliner-driven call-graph traversal, and GCC's list is comparable and different. The mechanism — passes with preconditions, run repeatedly because each exposes work for the others — is what transfers. The list and the ordering do not.

The passes are not run once. The manager loops over all enabled passes and repeats until a full round changes nothing, because each pass exposes work for the others. Folding produces a constant; propagation carries it into a branch condition; branch simplification turns the conditional into a jump; unreachable-block elimination removes the block that can no longer be reached; dead code elimination removes the definitions that block was the only user of. Five passes, each triggered by the one before.

The folding example shows the whole cascade in real numbers. let x = 2 * 3; let y = x + 0; if (false) { print(999); } print(y); starts at seven instructions and finishes at three, after two iterations of the pipeline, with six passes reporting a change: constant folding, strength reduction, constant propagation, branch simplification, unreachable block elimination and dead code elimination — one change each. The if (false) block and its print(999) are gone entirely, and print(y) has become print 6.

There is a maximum iteration count of twelve, and it is a termination guard rather than a tuning knob. In principle two passes could undo each other and oscillate; in practice these eight do not, and the cap exists so that a bug in a future pass produces a bounded compile rather than an infinite one. Real pass managers have the same guard for the same reason.

The pass set is a Set, not an ordered list, and that is deliberate. The order is the compiler's to choose, and different orders produce different code from the same passes — which is [[phase-ordering]], the observation that there is no order that is best for every program. Toggle passes off at /compilers/passes and watch: turning off constant propagation alone stops the branch from folding, which stops the block from being unreachable, which keeps five instructions alive that would otherwise not exist.

Toggle them yourself

The pass manager at /compilers/passes is the interactive that makes this lesson stick, because it turns a claim into an experiment. Every pass has a checkbox; the IR is recompiled on every change; and each pass that fired reports how many instructions it rewrote.

Three experiments worth doing in order. Turn everything off and read the raw lowering — it is longer than the source suggests, full of load and store against slots, because that is what a frontend actually emits before anything promotes locals into registers. Turn on only dead code elimination and watch how little happens: without constant propagation nothing became provably unused, which is the cleanest demonstration that passes enable each other rather than each doing an independent share. Turn everything on and load `trap` and confirm that the fold you would expect does not happen.

The fourth experiment is the best one and takes the longest: pick any example, turn passes on one at a time, and predict before each toggle what will change. Being wrong is the point — a wrong prediction is exactly where your model of what a pass requires differs from what it requires, and the legal field for that pass is the answer.

How it works

The steps, in the order the compiler takes them.

The optimizer clones the SSA function, so the unoptimized form remains available for the pipeline explorer to show alongside.
It loops: for each enabled pass in order, run it and record how many instructions or edges it rewrote.
A pass that changed nothing is not recorded; a round in which no pass changed anything ends the loop.
Constant folding evaluates a binary instruction whose operands are both literals, skipping any instruction for which mayTrap returns true.
Strength reduction rewrites algebraic identities that hold across the whole operand domain, which for integers includes x + 0 and x * 1.
Constant and copy propagation replace uses with the single definition SSA guarantees, then leave the now-unused definition for dead code elimination.
Branch simplification replaces a conditional branch whose condition is a literal with an unconditional jump, after which unreachable-block elimination removes anything no longer reachable from entry.
CSE walks in dominator order, keying pure instructions by opcode and operands, and replaces a later occurrence with the earlier value; DCE deletes any instruction for which hasEffect is false and whose result has no user.
The result records the pass runs, the iteration count, and the instruction count before and after, all of which the pass-manager UI renders.

How it breaks

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

A pass that deletes an instruction without consulting hasEffect, so a print whose result is unused vanishes and the program silently stops producing output.
A folder that does not consult mayTrap, so a program containing a never-executed 1 / 0 fails to build — a compiler rejecting a correct program because of a path it never takes.
CSE without a dominance check, replacing a value with one computed on a path that does not always execute, producing a use of an undefined value.
A propagation pass that assumes single definition on non-SSA input, silently using the wrong definition where two reach the same use.
Two passes that undo each other, so the fixed-point loop never converges and the compile hangs — which the iteration cap turns into a bounded, wrong-but-finite compile instead.
A pass reporting changes it did not make, so the loop runs to the cap on every compile and nobody notices except as unexplained slowness.
Reading the optimized panel as what the VM executes: the VM runs bytecode emitted from the pre-SSA IR, which is a different program.

When it helps

Learning what makes an optimization legal, with eight worked preconditions and two example programs that demonstrate refusal rather than success.
Seeing phase ordering as a real effect rather than a claim: toggling one pass changes what four others can do.
Understanding why SSA is worth constructing, by comparing the preconditions these passes need against what they would need on ordinary three-address code.
Building an optimizer, where "write the legality condition as a field before writing the pass" is a habit that catches exactly the bugs mayTrap was invented to catch.

When it hurts

As a model of a production pipeline. Eight passes against LLVM's hundred and fifty is not a difference of degree; the interactions and the ordering problem are qualitatively different at that scale.
For loop and memory optimization, none of which exist here: no hoisting, no unrolling, no vectorization, no alias analysis, because AtlasLang has no memory to alias.
For inlining, which is absent — and which in a real compiler is the pass that makes most of the others worth running.

What it costs

Every one of these is paid by something.

Running to a fixed point buys the cascade — each pass exposing work for the others — and pays by running every pass repeatedly, including the ones that will find nothing.
Carrying legality conditions as data buys a UI that cannot show a rewrite without its precondition, and pays by forcing every pass author to write the condition down before the pass exists.
Requiring SSA buys cheap propagation and a free availability condition for CSE, and pays the construction cost plus the out-of-SSA pass needed before code generation.
Treating every call as effectful buys unconditional correctness and pays by keeping calls whose results are unused, which a purity annotation would let the compiler remove.
A conservative mayTrap buys programs that build even when a never-taken path would fault, and pays by leaving foldable-looking arithmetic in the output.
An iteration cap buys guaranteed termination and pays by silently producing less-optimized code if a future pass ever needs a thirteenth round.

What else you could do

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

Sparse conditional constant propagation combines constant propagation and branch simplification into one algorithm that is strictly more powerful than running them separately to a fixed point, at the cost of being one larger pass instead of two small readable ones.
A fixed hand-tuned pass order, as production compilers use, which is faster than iterating to a fixed point and requires someone to have tuned it — [[pass-pipelines]].
E-graphs and equality saturation, which sidestep phase ordering by representing all rewrites simultaneously and extracting the best one, at a substantial cost in implementation complexity.
Peephole optimization over the bytecode instead of the IR, which would catch the STORE/LOAD pairs this optimizer never sees because it works on a different representation — [[peephole-optimization]].
No optimizer at all, which is what a debug build effectively is, and which keeps the correspondence between source and execution that all of these passes destroy — [[debug-vs-release]].

See it for yourself

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

/compilers/passes — toggle each pass and watch which instructions survive, with a change count per pass and the iteration count.
Load the trap example and confirm that 10 / 0 reaches the optimized output unfolded, then run it and read the fault message.
Load the effect example and confirm that print(42) survives with no reader while 1 + 1 disappears entirely.
Load folding and count: seven instructions to three, two iterations, six passes reporting one change each.
Turn everything off and read the raw lowering, which is the load/store form a frontend actually emits.
src/compilers/sim/optimize.ts — PASSES, hasEffect and mayTrap are all in the first quarter of the file, and the preconditions are fields rather than comments.

Plausible wrong readings

Stated the way a confident engineer states them.

"The optimizer removes code that does nothing." It removes code whose *value* nothing uses and which has no effect. Those are two conditions, and print fails the second while satisfying the first.
"10 / 0 should be a compile error." Then a program with an unreachable division by zero would fail to build. The compiler declines to fold it and lets it fault where it would have faulted.
"More passes means better code." Passes enable each other and can also undo each other, and no single order is best for every program. That is phase ordering, and it is why the cap exists.
"This is what the VM runs." The VM runs bytecode emitted from the pre-SSA IR. The optimized SSA panel is a different program, and a phi node is the reason.

Misconceptions

The claim, and what is actually true.

An optimization is a rewrite that makes code faster.

It is a rewrite that preserves observable behavior and is expected to make code faster. The first half is the requirement; the second is the hope, and only the first is checkable.

Dead code elimination removes code that never runs.

It removes instructions whose results are unused and which have no effect. Removing code that never runs is unreachable-block elimination, a different pass with a different precondition.

Constant folding always folds constants.

It folds constants whose operation cannot trap. 10 / 2 folds and 10 / 0 does not, and the difference is the entire content of mayTrap.

Running the passes once is enough.

Each exposes work for the others, which is why the manager iterates. On the folding example the cascade needs two full rounds to settle.

Go deeper

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

overview

The optimizer rewrites the program into something that does the same thing with less work: it computes constant arithmetic at build time, replaces variables with their known values, removes branches whose condition is known, and deletes anything nothing uses. Each of those is only allowed under a specific condition, and two conditions do most of the work — never delete something that prints, and never compute a division that would fault.

practical

Go to /compilers/passes and turn passes off one at a time. The thing to watch for is not what each pass does alone but what stops working when it is missing — turn off constant propagation and the branch stops folding and the unreachable block survives. If you are writing an optimizer, copy the one habit worth copying from this file: write the legality condition and a counterexample as fields on the pass before you write the pass. mayTrap exists because someone had to fill in illegalWhen for constant folding and could not do it honestly without it.

advanced

Two structural points are worth carrying away. First, three of these eight passes are trivial only because the input is SSA, and the same three are among the hardest passes to write correctly on ordinary three-address code — which is the real argument for SSA construction, better than any statement about elegance: it converts data-flow questions into lookups. Second, the pass set being a Set rather than a list is a small honesty about phase ordering. There is no order that is best for every program, and a fixed-point loop over an unordered set is one legitimate response — pay more compile time, stop caring about the order. Production compilers make the opposite choice, hand-tuning a fixed sequence because they cannot afford the iteration, and then live with the fact that some programs would have been better under a different one. Equality saturation is the third answer, representing every rewrite at once and choosing at the end, and it is expensive enough that almost nobody ships it. There is no fourth.

How much this depends on

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

implementationThe eight passes, their order, the iteration cap and the two guard predicates are AtlasLang's, in src/compilers/sim/optimize.ts at this revision. LLVM at -O2 runs on the order of a hundred and fifty pass instances in a tuned fixed order; GCC's list is comparable and different again. Neither the list nor the numbers transfer — the mechanism and the discipline of writing preconditions down are what do.

simplifiedAtlasLang has no floats, so x + 0 is unconditionally x; in IEEE-754 it is not, because it turns negative zero into positive zero, and a real strength-reduction pass must therefore be told whether fast-math relaxations are permitted. It has no heap, so there is no alias analysis and CSE over memory — the hard case — does not arise. And integers do not wrap, so there is no signed-overflow assumption for the optimizer to exploit, which removes the single largest source of surprising optimizations in C and C++.

specWhich rewrites are legal is decided by the language definition, not by the optimizer. AtlasLang defines only print output and division faults as observable, which is why this optimizer can be aggressive. C defines far more as observable and simultaneously leaves far more undefined, so its optimizers are both more constrained and more licensed than this one, in different places.

If you were asked this in an interview

Why does the optimizer delete 1 + 1 and keep print(42) when neither result is used?
Why is 10 / 0 not folded, given that the program is going to fault anyway?
Which of these passes get cheaper because the input is in SSA form, and what would each need without it?

Connections

DSAdag dfs hash-table topological-sort

Computer Architectureinteger-overflow floating-point-precision

Domains that do not exist yet

Testing & Reliability Engineering — Differential and property-based testing of a transformation against an unoptimized reference
Every pass here is a rewrite that must preserve observable behavior, which is a property a generator can attack: compile with passes on and off, run both, compare output. The technique belongs there; the reason an optimizer specifically needs it — that its bugs produce wrong answers rather than errors — is here.

Runtime gain3

Compile cost2

Debuggability2

Implementation3

Context dependence3

Runtime gain is 3: these passes genuinely shrink the instruction count on the example programs, and they are also the eight cheapest wins in any optimizer rather than the ones that produce large speedups. Compile cost is 2 because the fixed-point loop runs every enabled pass repeatedly, which is affordable only at this scale. Debuggability is 2 — every pass here destroys some correspondence between the source and the running code, which is the standing price of all of them. Implementation complexity is 3: each pass is short, and getting the two guards right is where the difficulty actually is.

Try it

pass manager →pipeline explorer →atlaslang playground →