Syntax trees, stack code, and three-address code expose different information.
By the end: Explain lowering, explicit temporaries, and static single assignment without confusing source variables with compiler values.
An intermediate representation, or IR, is a compiler’s internal language for a phase of processing. An AST keeps source-like structure. Three-address-style code names individual results, such as t1 = 3 * 4 followed by t2 = 2 + t1. Stack code makes operand placement implicit in stack order instead.
Lowering translates a higher-level construct into more explicit operations. A for loop might become initialization, a test, a body, and a back edge. An array access may become an address calculation plus a bounds check and a load. What must remain explicit depends on the language semantics and the next analysis.
An intermediate representation makes some relationships explicit and leaves others implicit. Consider x * (2 + 3), whose multiplication depends on a name read and an addition. Its syntax tree expresses that dependency through child edges. A tree evaluator returns five from the addition subtree, then combines it with the value of x. Three-address pseudocode can instead name the addition result t1 and the multiplication result t2. These names describe computed values, not declarations that the learner must add to the source program.
To preserve the specified left-before-right evaluation order, a fully explicit translation first reads x into v0, then computes t1 = 2 + 3, then t2 = v0 * t1. With the fixed environment, v0 holds four, t1 holds five, and t2 holds twenty. SmallExpr has no effects that would distinguish moving this particular name read past the literal addition, but writing the read explicitly exposes the ordering decision. In an effectful language, a superficially similar rearrangement might need an additional proof about state changes.
The stack representation records the same dependency without naming t1. LOAD x leaves four on the stack. PUSH 2 and PUSH 3 extend it to four, two, three, listed bottom first. ADD removes the top pair and leaves four, five. MUL replaces those values with twenty. Five instructions execute, even though the tree has only two arithmetic operators. Loading values is work in this instruction vocabulary. Neither five instructions nor two arithmetic operators specifies elapsed time on an actual processor or a different virtual machine.
Now compare x - (y - 1), using the fixed values four and seven. A named-value translation reads x, reads y, subtracts one from y to obtain six, and subtracts six from x to obtain negative two. Stack code must leave four below seven and one before its first SUB. That instruction pops one as the right operand and seven as the left. Addition would conceal a reversal because its operands commute. Subtraction makes an incorrect translation visible through a different returned value.
Use the representation comparison on this page as a tracing exercise rather than as an editable SSA compiler. Its expression is 2 + 3 * 4. Cover the final result and locate the multiplication dependency in each form. In the tree, follow the right child of addition. In the named code, find the use of t1. In the stack code, identify the twelve left by MUL. Each route must explain why addition receives twelve rather than an unevaluated multiplication instruction or the original source characters.
| Completed instruction | Stack, bottom first | Meaning |
|---|---|---|
| LOAD x | 4 | Left operand of outer subtraction |
| LOAD y | 4, 7 | Left operand of inner subtraction |
| PUSH 1 | 4, 7, 1 | Right operand of inner subtraction |
| SUB | 4, 6 | 7 − 1 = 6 |
| SUB | −2 | 4 − 6 = −2 |
A useful translation check pairs states at matching semantic points, not matching line numbers. Immediately after the multiplication in that comparison, the named form has t1 equal to twelve, while the stack form contains two and twelve. The extra two is an already evaluated sibling, awaiting addition. After the final addition, both forms return fourteen. Intermediate states need not look identical. They must represent the information needed to complete equivalent computations under the same integer rules and the same bindings.
A source variable may be assigned many times, but the compiler can give each computed value a distinct name. In static single assignment form, each SSA name has one definition. A loop still executes repeatedly; the restriction applies to definitions in the static representation, not to the number of dynamic executions.
At a control-flow join, an SSA phi operation selects the incoming value associated with the predecessor edge taken. It does not average values or independently evaluate both branches. A loop header can use a phi to choose an initial value on entry and an updated value on the back edge.
Static single assignment gives each named compiler value one definition site. Start with separate conditional pseudocode, not an expression accepted by SmallExpr. Suppose a boolean condition chooses between assigning ten and twenty to a source variable result, after which the program adds one. Simply renaming the two assignments result1 and result2 leaves a question at the later use. Which name should the addition read? The source variable had one spelling, but the lowered representation must express the dependence on the chosen control-flow path.
Introduce a join value result3 = phi(left: result1, right: result2). The labels left and right identify predecessor blocks, not argument positions chosen by chance. If execution arrives from left, result3 receives ten and the later addition produces eleven. Arrival from right gives twenty and then twenty-one. Only one branch executes in this example. A phi does not run the other branch to discover its value. Its alternatives describe which existing value is available on each possible incoming edge of the graph.
Contrast that selection with result1 + result2. The sum would require both values in the same execution, yet each branch defines only its own value. Even if an implementation happened to reserve storage for both, an unexecuted assignment would not supply the missing value. A phi expresses conditional availability rather than arithmetic combination. Its inputs must match the incoming paths and have compatible types under the chosen IR rules. The example uses integer values on both paths and a separately supplied boolean branch condition.
Loops require the same distinction between a static definition and a dynamic value. In a counting-loop sketch, let the header define i = phi(entry: 0, body: next), then test i < 3. The body defines next = i + 1 and returns to the header. The first header visit chooses zero through the entry edge. Later visits choose one, two, and three through the back edge. There is one written definition of i, but each execution of that definition yields the value for that visit.
Trace the last visit carefully. After the body computes next equal to three, control returns to the header. The phi selects three before the comparison runs. The comparison fails, so the body does not compute four. Writing an SSA loop therefore does not imply that all instructions execute exactly once, or that every possible input has already been evaluated. The graph states where execution may go. The phi states which incoming value a particular arrival uses. Dynamic execution supplies the particular sequence of arrivals.
As a paper exploration, swap the two predecessor labels in the conditional phi while leaving both branches unchanged. A left arrival now requests the value defined only on the right path. That is a representation error, not an alternative optimization that merely changes the answer. Repair the labels, then change the right literal to thirty. Only the right outcome should become thirty-one. This separates a structural obligation about valid incoming definitions from a numerical claim about one run, and neither exercise requires the page to implement an SSA transformation pass.
// Three-address pseudocode for 2 + 3 * 4
t1 = 3 * 4
t2 = 2 + t1
return t2t1 = 3 * 4
t2 = 2 + t1
return t2PUSH 2
PUSH 3
PUSH 4
MUL
ADD| Representation | Where the temporary result lives |
|---|---|
| AST | Value returned from the multiplication subtree |
| Three-address code | Named temporary t1 |
| Stack bytecode | Operand-stack entry |
Lowering changes the operations used to express a computation. It can turn one source construct into several simpler operations, each with a defined role. In separate array-access pseudocode, reading a[i] may require checking an index, computing an address, and loading a value. Whether a bounds check is required belongs to the source language contract. Whether the address uses a scaled-index instruction belongs to the target and backend. Treating both questions as one translation step hides which decisions preserve meaning and which select a machine representation.
For a concrete checked-array model, assume three elements, each four bytes, beginning at byte address 1000. Index two is valid because it is nonnegative and smaller than three. Its element begins at address 1008, computed as the base plus two times four. Index three would produce address 1012 arithmetically, but the language rule rejects it before a load. A plausible address calculation does not establish permission to read. These invented addresses illustrate the check and offset mechanism, not an actual SmallExpr heap or a real allocation.
The lowering must preserve failure behavior as well as successful values. Suppose an invalid index must raise a bounds error without reading memory. Replacing the checked access with an unconditional load changes the contract, even if all observed tests used valid indices. Conversely, a compiler can remove the check if static analysis proves the index valid whenever the access executes. That proof is about all executions covered by its assumptions. One successful dynamic read at index two cannot establish it for an unknown future index.
Arithmetic semantics also belong in the representation. SmallExpr wraps every integer operation to signed thirty-two-bit results. Its supported expression 999 * 999 * 999 * 999 first yields 998001, then 997002999, and finally negative 426416671 after wrapping. A named-value form and stack code must agree at these operation boundaries. Merely labeling a temporary int does not justify replacing wrapping operations with arithmetic that traps on overflow or assumes overflow never happens. Such replacements would require a different contract or a proof that overflow is impossible.
Consider a hypothetical target that cannot directly multiply two values of the IR's width. A backend could implement the operation with several narrower instructions, provided their combined result matches the required bits. This is a target constraint, not a change to the source language's integer range. The reverse situation also occurs. A target may combine address calculation and loading in one instruction, while the IR keeps them separate for analysis. Counts measured at these two representation levels therefore answer different questions about how the computation is expressed.
| Index | Check for length 3 | Permitted next action |
|---|---|---|
| 0 | 0 ≤ 0 < 3 passes | Read the element at byte address 1000 |
| 2 | 0 ≤ 2 < 3 passes | Read the element at byte address 1008 |
| 3 | 3 < 3 fails | Raise bounds error; do not load |
| −1 | 0 ≤ −1 fails | Raise bounds error; do not load |
Explore the array example by changing the index on paper to zero, then negative one. Zero passes the assumed check and selects address 1000. Negative one fails the lower-bound check, so the modeled execution stops before reading address 996. Next imagine removing the check because the only recorded run used zero. Identify the missing proof before discussing speed. The proposed transformation needs a fact about all allowed indices at that point, not an attractive instruction count or an address that happens to fall near the array.
An IR is not merely a convenient printout. Its instructions, types, control edges, and ownership rules have meaning. A transformation that leaves a use without a valid reaching definition or creates an invalid branch target has damaged the representation even if the text looks plausible.
Compilers often maintain several IR levels rather than force every task into one. Source-level structure helps diagnostics; explicit control and data flow support optimization; target-specific forms express registers and instruction constraints. Our bytecode lab is one IR example, not LLVM IR or a general SSA implementation.
An IR verifier checks whether the representation obeys its own construction rules. For a named-value graph, useful questions include whether every use names a definition, whether operand types agree, and whether control flow makes the definition available. In straight-line code, t2 = t1 * 4 cannot read t1 before any instruction defines it. A verifier can reject that structure without choosing numeric inputs. Passing these checks establishes structural validity under the IR rules, not that the compiler translated the source correctly or produced efficient code.
A well-formed but incorrect translation is easy to construct. Start with 8 - 3 - 1, whose left-associated tree returns four. Generate a right-associated subtraction sequence instead, computing three minus one and then eight minus that result. Every instruction has enough integer operands, and the final stack has one value. The code returns six, so it violates the source meaning despite satisfying the local stack rules. Structural verification and semantic preservation address different failure modes. A reliable investigation asks which kind of evidence a particular check supplies.
For stack bytecode, count the stack effect of each instruction. PUSH and LOAD increase height by one. NEG leaves height unchanged but requires an integer value. Each binary arithmetic instruction needs two integers and reduces height by one. For the correct left-associated subtraction, heights after successive instructions are one, two, one, two, one. Ending at one is necessary, but checking only the endpoint misses underflow earlier in a malformed sequence. A proper boundary check also tracks the required operand types rather than treating all occupied cells as interchangeable.
| Instruction number | Left-associated code / height | Right-associated code / height |
|---|---|---|
| 1 | PUSH 8 / 1 | PUSH 8 / 1 |
| 2 | PUSH 3 / 2 | PUSH 3 / 2 |
| 3 | SUB / 1 | PUSH 1 / 3 |
| 4 | PUSH 1 / 2 | SUB / 2 |
| 5 | SUB / 1 | SUB / 1 |
| Returned value | 4, correct for 8 - 3 - 1 | 6, correct for 8 - (3 - 1) |
Now follow a small valid transformation. The literal subtree in x * (2 + 3) has no name reads and computes five under the same wrapping rules, so the numeric constant folder can replace it with five. The surrounding multiplication still reads x. In the fixed environment, both versions return twenty. The original stack program uses five instructions and the folded one uses three. The reason for equivalence is the subtree's specified value, not merely the observed agreement at x equal to four or the smaller count.
An analysis describes facts; a transformation changes the representation using those facts. Finding a constant subtree is analysis. Replacing it is transformation. Rechecking types and stack behavior afterward can expose a broken rewrite, but cannot by itself prove every valid-looking replacement equivalent. For example, replacing the entire expression with twenty passes those checks yet specializes away the name read. It agrees in the displayed environment but does not establish equivalence for other integer bindings. The implemented folder deliberately keeps names rather than inferring constants from the current demonstration values.
| Check | Established fact | Still unproved |
|---|---|---|
| IR verification | Definitions, types, and edges obey the IR rules | Equivalence to the source |
| Literal-folding argument | 2 + 3 has the same integer value as 5 | A claim that names are constants |
| One run with x = 4 | Both forms returned 20 in this environment | Agreement for other bindings |
| Five instructions become three | This bytecode stream is shorter | Lower elapsed time on a real target |
Finish by auditing a proposed copy of the representation comparison. If someone changes t2 = 2 + t1 to t2 = 2 - t1, the names remain defined and the types remain integers. Nevertheless, the result becomes negative ten instead of fourteen. Locate the first changed semantic operation and match it to the source tree. Then restore addition and ask whether t1 needs a physical register. The IR name alone does not decide that question. Storage assignment and target instruction selection are later responsibilities with additional constraints.
One predecessor assigns t1 = 10; another assigns t2 = 20. A join has t3 = phi(left: t1, right: t2). What is t3 after arrival from the right?
A phi is indexed by the incoming control-flow edge.
| Incoming edge | Selected value |
|---|---|
| Left | t1 = 10 |
| Right | t2 = 20 |
It is twenty, the value associated with the right predecessor. The phi does not add, average, or choose based on which assignment is textually closer. Its meaning depends on the actual predecessor edge.
A loop executes the same addition instruction many times. Is that incompatible with SSA?
Distinguish a static definition site from repeated dynamic execution.
| Concept | Counts |
|---|---|
| Static definition | One site in the representation |
| Dynamic execution | Potentially many visits |
| Loop-carried value | Connected through the appropriate phi |
No. One static SSA definition can execute on every loop iteration. Phi operations express which iteration’s values reach the next iteration. SSA is about definition structure in the IR, not a rule that every instruction may execute at most once.
The explanations, examples, and worked answers are complete without these optional links. The sources describe specific implementations and language contracts, not one universal compiler pipeline. SmallExpr and the later pseudocode models are constructed teaching examples. Source notes identify the selected material reviewed; this is not an exhaustive compiler survey, production conformance test, or independent specialist review.
Selected material on IR structure, SSA, phi semantics, integer operations, and semantic constraints. A production IR reference, not a specification of SmallExpr or a claim that every compiler uses LLVM.
Selected overview and register-allocation material describing instruction selection, target constraints, liveness, and native-code generation. The storage lab is not an implementation of LLVM’s allocator. The reviewed register-allocation example has inconsistent def/use prose; the lesson follows explicit assignment direction instead.