- Compilers: Principles, Techniques and Tools — Ch. 6 §6.3 (types, declarations and storage layout), §6.4.3 (addressing array elements), §6.5 (type checking), §6.9 (intermediate code for procedures); Ch. 7 §7.1 (storage organization), §7.2 (stack allocation), §7.3 (access to nonlocal data). Review §2.7 and §5.1–5.3.
- §1.6.6 on parameter passing is two pages and settles the by-value / by-reference question you will otherwise argue about for an hour.
- Browse §8.3, on how the symbol table's offsets become addresses in the target code.
0Where this topic sits
Topic 2 gave every variable a slot in one flat region, because there was only ever one thing running. This topic breaks that assumption three times over. Arrays mean a name can occupy many slots. Functions mean several activations can be alive at once, each needing its own storage. Scope means one name can refer to different storage in different places.
The theory that handles all three is the run-time environment: the set of conventions about where data lives and who is responsible for it. Dragon devotes a whole chapter to it, and it is the single largest conceptual step in the course.
1Types, declarations, and storage layout
A declaration does two jobs (Dragon §6.3): it records a name's type in the symbol table, and it reserves storage. The type determines how much.
Types are built inductively, exactly like regular expressions were. A type expression is either a basic type, or a type constructor applied to type expressions (§6.3.1):
basic types int float char boolean void
constructors array(n, T) n elements of type T
record( ... ) named fields
pointer(T)
T₁ × T₂ → T a function
int scores[10] is array(10, int)
int sum(int a[]) is array(?, int) → intStorage follows from the type. Dragon §6.3.2 computes it with two attributes carried through the declaration list — a type and a width — and a running offset that starts at zero and advances by the width of each declared name. That is precisely what our symbol table does, and it is a textbook example of an inherited attribute doing useful work.
Dragon §6.3.2 notes that many machines require a multi-byte object to sit at an address divisible by its size, so compilers insert padding between fields. Our language has only int, all four bytes wide, so every offset is naturally aligned and the issue never arises. It arises immediately if you add char as an optional extension — and it arises in the .data section regardless, which is why the generated assembly contains .align 2 directives.
2Arrays: indexing is address arithmetic
Dragon §6.4.3 derives array addressing from first principles, and the derivation is worth following because everything else about arrays follows from it.
base + i×w and then loading or storing. The only genuinely interesting question is where base comes from, and that has three different answers.For one dimension the formula is base + i × w. Note that i × w is a multiplication in a loop, and that w is a power of two — so a compiler emits a shift instead. That is strength reduction (Dragon §9.1.8) appearing already, and it is the first optimization in your back end even though phase 5 has not run.
For k dimensions the addresses come from a recurrence, and computing them requires the compiler to remember the array's bounds — which are part of the type, not part of the value. This is the reason C makes you write int m[][4] rather than int m[][] in a parameter list: without the column count the callee cannot compute an address.
Where does base come from?
This is the only part that is not arithmetic, and it has three answers depending on where the array lives:
| Kind of array | Where the elements are | How the base is obtained |
|---|---|---|
| global | the static data area | the address of a label — known at link time |
| local | this activation record | stack pointer plus a compile-time offset |
| parameter | somebody else's frame, or the data area | read out of the parameter slot — it is a pointer |
Dragon §1.6.6 distinguishes call-by-value from call-by-reference. Ours passes integers by value and arrays by reference — as C does, and for the same reason: copying an array on every call is expensive, and the copy is almost never wanted. The consequences are worth stating explicitly. The callee's slot holds one word regardless of the array's size. The callee cannot know the length, so every function taking an array also takes a count. And a write through the parameter modifies the caller's array — which is either a feature or a hazard, depending on the day.
3Scope
The scope of a declaration is the region of program text in which it applies (Dragon §1.6.3). When several declarations of the same name are in scope, the most closely nested rule decides which one a use refers to.
Implementing this needs no cleverness: a stack of tables, pushed on entering a block and popped on leaving, with lookup searching from the top. Shadowing then falls out of the search order rather than needing to be programmed (Dragon §2.7.1).
Static scope and dynamic scope
Ours is statically (lexically) scoped: which declaration a use refers to is determined by the program text, and can be settled at compile time. The alternative is dynamic scoping, where a use refers to the most recent declaration made by any currently active procedure — a run-time question (Dragon §1.6.5, §7.3). Almost every modern language chose static scoping, because it lets a reader determine what a name means without simulating execution.
Access to non-local data
Dragon §7.3 covers the harder case: a procedure nested inside another, referring to a variable of its enclosing procedure. Solving it needs access links or a display. Our language has no nested procedures, so the problem does not arise — a name is local, a parameter, or global, and nothing else. Knowing what the access link is for is enough; you will meet it again in any language with closures.
4Run-time storage organization
Dragon §7.1 divides run-time memory into four areas, and which area a name lands in is decided entirely by its lifetime:
| Lifetime | Area | Allocated by | In our language |
|---|---|---|---|
| the whole program run | static | the compiler, at compile time | globals — emitted into .data |
| one activation of a procedure | stack | the calling sequence, at run time | parameters, locals, temporaries |
| arbitrary — outlives its creator | heap | an explicit allocator | none; we have no malloc |
This is the whole reason global and local variables are generated so differently. It is not an implementation quirk — it is the lifetime of the name deciding which storage discipline can serve it.
5Activation records
Every execution of a procedure is an activation, and every activation needs somewhere to keep its parameters, locals and bookkeeping. That somewhere is an activation record, or frame (Dragon §7.2).
The key observation (Dragon §7.2.1) is that activations nest: if activation b begins while a is running, then b finishes before a does. That is exactly the discipline of a stack — which is why activation records go on a stack, and why the design generalizes to recursion without any extra machinery.
$sp always points at its base. Read left to right, this is a depth-first traversal of the activation tree above — which is the correspondence that makes a stack the right data structure.- $ra is not saved. Works for one call. Breaks the moment a function calls another function, because
jaloverwrites the return address. Symptom: the program returns to the wrong place, or loops. - No new frame is pushed. The callee's locals land on top of the caller's. Symptom: a caller's variable changes value across a call, for no visible reason.
returnfalls through instead of jumping to the epilogue. Symptom: a function with areturnin the middle always returns whatever the LAST return statement says.
6The calling sequence
Allocating and freeing a frame is a joint operation. Dragon §7.2.3 calls the code that does it the calling sequence, split between the caller and the callee.
Two design principles govern the split (Dragon §7.2.3), and both are worth being able to state:
- Put as much as possible in the callee. The callee's half of the sequence occurs once in the program; the caller's half occurs at every call site. Moving work into the callee shrinks the program.
- Fields whose size is not known to the caller go near the top of the frame. Then the caller can compute offsets to the fields it does know about, without knowing the callee's local storage requirements at all.
Register conventions
A calling convention must also say what happens to registers, and there are only two possible answers per register. Caller-saved: the callee may destroy it, so the caller writes back anything it still needs. Callee-saved: the callee must preserve it, saving and restoring it if it wants to use it. MIPS convention makes $t0–$t9 caller-saved and $s0–$s7 callee-saved. Ours uses only the caller-saved set, which is why every live value is written back before a jal.
Why does the calling convention put the return address in a register ($ra) and then require the callee to save it to memory, rather than having jal push it onto the stack directly?
7Intermediate code for procedures
Dragon §6.9 shows what a call becomes in three-address code — a short, deliberately machine-independent sequence:
source three-address code
─────────────────────────────
n = f(a[i]); t1 = i * 4
t2 = a [ t1 ]
param t2
t3 = call f, 1
n = t3Note what the IR does not say: nothing about registers, nothing about the stack, nothing about who saves what. All of that is the back end's business. param means 'here is an argument', and call f, 1 means 'transfer control to f, which takes one argument'. That is the front end's entire contribution to the calling convention, and it is why retargeting does not touch phase 4.
8Two passes, and why
This program is legal, and forcing it to be legal is a decision:
int main() {
print(helper(3)); <- used here …
return 0;
}
int helper(int x) { <- … defined here
return x + 1;
}A single traversal would reach the call before ever seeing the definition, so it could not check the argument count. Two passes fix it: the first records every function's signature, the second checks the bodies. This is a small instance of a general pattern — when a check needs information from later in the program, either make a preliminary pass to collect it, or require the programmer to supply it in advance.
C chose the second: it required forward declarations precisely so that one-pass compilation stayed possible on 1970s hardware. That constraint is gone, and modern languages generally do not impose it. Either answer is defensible in your compiler; not knowing which you implemented is not.
9Type checking, briefly
Dragon §6.5 builds a type checker as a syntax-directed definition: a synthesized attribute type on every expression node, and rules that combine children's types and report a mismatch. With only int in the language there is nothing yet to mismatch — but the shape is worth seeing, because it is where an optional extension would go:
E → E₁ + E₂ { E.type = (E₁.type == integer and E₂.type == integer)
? integer : type_error }
E → E₁ [ E₂ ] { E.type = (E₁.type == array(s, t) and E₂.type == integer)
? t : type_error }Two ideas from that section are worth carrying even without a type system. Type conversion: when operand types differ, a compiler may insert a coercion — the inttofloat you saw in Topic 1's running example. And type equivalence: does a name for a type mean the same as its definition? Structural versus name equivalence is a real language decision and a good interview question.
10The approach for this milestone
Do arithmetic and arrays first, functions second
The first two are additive — new cases in switch statements you already wrote. Functions change what the code generator has to promise, and will take longer than the other two combined. Budget accordingly.
Draw the frame before you generate it
On paper, for one small function: every slot, its offset, and the total size. Then compare with what the compiler reports. This takes ten minutes and saves an evening of reading generated assembly hoping something jumps out.
Decide the frame layout once, and write it down
Where does $ra go? Do offsets grow up or down from the stack pointer? Where do temporaries live? These are arbitrary choices, but they must be made once and honored by the prologue, the epilogue and every load and store. A comment diagram at the top of the code generator is worth more than any amount of debugging later.
Keep the two symbol tables separate in your head, and in your files
Visibility is a phase-3 question; storage is a phase-6 question. They have different lifetimes, different shapes, and different contents. Students who conflate them cannot debug either one.
Test recursion early
fact(5) returning 120 exercises the entire calling convention in one line. If it returns anything else, stop and fix the convention before writing another feature — everything downstream depends on it.
11Self-check
Why are activation records kept on a stack rather than in a list or a table?
int a[5]; is a local at frame offset 12. What is the address of a[3], and how many bytes does the array occupy?
A function takes int a[]. How many bytes does that parameter occupy in the callee's frame?
Which task belongs to the CALLER rather than the callee, and why?
Your compiler has a scope stack in semantic.c and a symbol table in symtab.c. Why not merge them?
12References
- Aho, Lam, Sethi & Ullman, 2nd ed. — §1.6.3–1.6.6 (scope, static vs dynamic, parameter passing); §2.7 (symbol tables and scope); §6.3 (types, declarations, storage layout and alignment), §6.4.3 (addressing array elements), §6.5 (type checking, conversions, equivalence), §6.9 (intermediate code for procedures); §7.1 (storage organization), §7.2 (activation trees, activation records, calling sequences, variable-length data), §7.3 (access to nonlocal data, access links, displays); §8.3 (addresses in the target code).
- Patterson & Hennessy, Computer Organization and Design, ch. 2 — the MIPS procedure call convention from the architecture's side.
- The MIPS o32 ABI documentation, for what a real convention specifies that ours leaves out.