- Compilers: Principles, Techniques and Tools — Ch. 1 §1.4 (the science of building a compiler) and §1.5 (applications of compiler technology), now that you have built one; review Ch. 4–9.
- Skim the openings of Ch. 10 (instruction-level parallelism) and Ch. 11 (optimizing for parallelism and locality) — not to implement anything, but to see where the subject goes next.
- §6.2.4 on SSA and §8.8.4 on graph coloring are the two most rewarding sections to read once your own compiler works.
0Where this topic sits
The language is complete. Nothing in this topic adds syntax. What it adds is the three things that separate a working project from a piece of engineering: numbers you can defend, documentation a stranger can use, and an honest account of the limits.
Dragon §1.4 calls this the science of building a compiler, and the phrase is not decoration. The discipline is: build an abstraction, choose a mathematical model that fits it, and then be honest about where the model stops applying. You have done the first two five times this semester. This topic is the third.
1What you actually built
Six phases, roughly three thousand lines, and — the part worth being proud of — about eighty-five per cent of it does not know what machine it targets. That is not an accident of how the files were divided; it follows from placing an intermediate representation between the front and back ends in week one, and it is the single most consequential structural decision in the whole design.
It is worth restating what each phase contributed, because the Benchmark asks you to explain the whole thing and the account is easy to give badly:
| Phase | The abstraction it introduced | The model behind it |
|---|---|---|
| 1 · Lexical | the token | regular expressions and finite automata |
| 2 · Syntax | the syntax tree | context-free grammars and LR parsing |
| 3 · Semantic | the symbol table and scope | syntax-directed definitions; attribute evaluation |
| 4 · Intermediate | three-address code | the machine-independent instruction set |
| 5 · Optimization | the transformation, applied to a fixed point | iteration to convergence (data-flow, in the general case) |
| 6 · Code generation | the activation record and the register cache | the calling convention; storage allocation |
Every one of those is an abstraction plus a model. That pairing is the method of the field, and it is why compiler construction is one of the few areas of software engineering with genuine theory behind it (Dragon §1.4.1).
2Two performance questions, and not confusing them
The Benchmark project asks for compilation time and execution time. They are different questions with different subjects, different tools and different units, and the most common failure in the write-up is answering one and labeling it the other.
3Measuring the compiler
Your driver already reports per-phase timings. One number tells you very little; the shape as input grows tells you a great deal.
Most phases here are linear in the size of their input, which is what you would hope: scanning is linear by construction (Topic 1 §6), LR parsing is linear in the number of tokens, and a tree walk is linear in the nodes. The optimizer is the exception. It runs several passes, and its dead-code test scans forward from each instruction, so in the worst case it is quadratic in the length of the TAC.
Noticing that your own optimizer is super-linear, measuring it, and saying what would fix it — a liveness analysis, which computes the same information once for the whole function instead of rescanning per instruction — is exactly the kind of observation Project 6 is asking for. It is worth far more than a paragraph restating that optimization takes time.
Amdahl's law
Before optimizing anything, measure where the time goes. The instinct to improve the part you find most interesting is almost always wrong, and this applies as much to your compiler as to the programs it compiles.
4Measuring the generated code
Here the subject is the .s file, and the honest metric is instructions executed.
It models the instruction set, not the machine: no pipeline, no caches, no memory latency. Wall-clock seconds from SPIM tell you about your laptop and the simulator, not about your compiler. Instructions executed is deterministic, exactly reproducible, and directly attributable to the code you generated — which is what makes it the right thing to report.
What makes a measurement defensible
- A stated baseline. 'Thirty per cent faster' invites the question than what? Say: optimized versus unoptimized output of the same compiler, same source, same simulator.
- A stated benchmark. A result on a program with a hot loop is a result about hot loops. Include the source in the report.
- Repetition and a spread. Three runs minimum. If the run-to-run spread is eight per cent, a five per cent improvement is not a result — it is noise, and reporting it as a result is the thing a reviewer will notice first.
- The metric named. Code size and work done are different questions. Report both and explain the gap; the explanation is worth more than either number.
These four rules are not specific to compilers. They are what makes any performance claim checkable, and the Benchmark is partly assessing whether you can make one.
5Knowing the limits
Every compiler has limits. The difference between a student project and a piece of engineering is whether the author can list them, say why each exists, and say what lifting it would cost. Here are this design's, and each is a decision rather than an oversight:
| Limit | Why it exists | What lifting it would take |
|---|---|---|
| At most four arguments per call | arguments are passed only in $a0–$a3 | pass the rest on the stack; decide who pops them (Dragon §7.2.3) |
| No array bounds checking | no length information survives to run time | carry the length with the array, or pass it; then a compare and a branch per subscript |
int is the only type | the type is recorded at declaration and never used again | a real type field, and type rules in phase 3 (Dragon §6.5) |
| Registers flushed at every branch | the allocator has no liveness information | build the flow graph, compute liveness (Dragon §9.2) |
| The optimizer forgets everything at a label | no analysis across basic blocks | the same flow graph, then reaching definitions |
| No recursion into expressions with side effects | eager evaluation of && and || | flow-of-control translation of booleans (Dragon §6.6) |
t0, L0 … are reserved identifiers | they would collide with generated names | prefix generated names with a character the scanner cannot produce |
'Three things you would do differently' is a design review, not a confession. Pick one from the compiler's architecture, one from the language's feature set, and one from your implementation. For each, say what the alternative was, what it would have cost, and why you decided as you did. A confident, accurate account of a limitation reads far better than a claim that there are none.
6What a production compiler does that yours does not
Three of those are worth a paragraph each, because they are the natural next steps and because knowing what they are makes your own design legible as a set of choices.
Static single assignment
SSA (Dragon §6.2.4) requires every variable to be assigned exactly once. Where control paths merge, a φ-function selects among the versions. The payoff is that the definition reaching any use is unique by construction, so optimizations that would otherwise need a reaching-definitions analysis become almost trivial. Every serious modern compiler — GCC, LLVM — is built on it. Placing the φ-functions needs the flow graph, which is why it belongs after Topic 4's machinery, not before.
Register allocation by graph coloring
Dragon §8.8.4 builds an interference graph: one node per value, an edge between values that are simultaneously live. Assigning k registers without two live values sharing one is exactly k-coloring that graph. The problem is NP-complete, so real allocators use Chaitin's heuristic — repeatedly remove a node with fewer than k neighbors, then color on the way back — and spill what cannot be colored. Ours has no liveness information at all, which is why it caches and evicts instead.
Instruction scheduling
On a pipelined processor the order of instructions matters as much as their number: a load followed immediately by a use of its result stalls. Reordering to fill those slots is instruction scheduling, and on real hardware it is often worth more than any of the transformations in Dragon §9.1. SPIM does not model a pipeline, so the effect is invisible here — which is itself worth knowing when you read a benchmark result.
7Errors, across all six phases
It is worth taking one last look at error handling as a whole, because Project 6 asks you to demonstrate it and because the six phases catch genuinely different things:
| Phase | Catches | Example | Why no earlier phase could |
|---|---|---|---|
| 1 · Lexical | characters the language does not admit | x = y @ z; | there is no earlier phase |
| 2 · Syntax | token sequences no production matches | int int int; | the scanner sees one lexeme at a time and no context |
| 3 · Semantic | context-sensitive rules | undeclared variable; wrong argument count; break outside a loop | no context-free grammar can express these (Topic 2 §8) |
| 4–5 · IR | internal inconsistencies | a temporary with no definition | these are compiler bugs, not program errors |
| 6 · Codegen | target limitations | more than four arguments | the limit is a property of the machine and the convention |
That fourth row is worth dwelling on. Errors detected in phases 4 and 5 are almost always your bugs rather than the programmer's, and should be reported differently — an internal-error message naming the compiler, not a diagnostic blaming the source. Compilers that confuse the two are infuriating to use.
8Documentation as an engineering artefact
A README is not a courtesy. Its test is operational, and it is a hard test: can somebody who has never seen your compiler build it and run it from your README alone, with no conversation?
Almost every README fails on the same four things:
- No exact build command. 'Compile the source files' is not a command.
makeis. - No versions. bison 2.3 and 3.x differ in ways that break grammars. Say which you used and on what OS.
- No runnable example. A README with no worked example cannot be checked by the reader, which means it cannot be trusted.
- No limitations section. Its absence tells the reader you did not look — and they will find the limits in about thirty seconds by running the tests.
The cold-start test in this week's activity is the only reliable way to find these. Reading your own README does not work, because you already know what it left out.
9The retrospective
Lab Questions 29 and 30 ask what you would do differently and what you are proudest of. Both are better answered structurally than emotionally. Some prompts that produce good answers:
| Layer | Question worth asking |
|---|---|
| Architecture | Which phase boundary earned its keep? Which one would you draw differently, and what would that have cost elsewhere? |
| Language design | Which feature was hardest to compile, and was it worth having? Which omission did you most regret? |
| Implementation | Which data structure would you change? Where did a shortcut in week 3 cost you a day in week 12? |
| Process | How did you divide the work? What would you divide differently, and why? |
A specific, technical answer — 'the AST's statement list should have been a vector, because every visitor needed a special case for a nested list, and I got that wrong twice' — is worth ten general ones.
10Where this goes next
Dragon §1.5 lists what compiler technology is actually used for beyond compilers, and it is a longer list than most people expect:
- Implementing high-level languages. The obvious one, and the reason abstraction is affordable at all.
- Designing new architectures. RISC exists partly because compilers, not humans, became the main consumers of instruction sets. Architecture and compiler design have co-evolved for forty years.
- Program translations. Binary translation, hardware synthesis from HDLs, database query compilation, source-to-source migration.
- Software productivity tools. Type checkers, linters, static analyzers, refactoring engines, IDE autocomplete — all built on parsing and data-flow analysis, both of which you have now implemented.
The last of those is the most immediately useful. A linter is a front end plus a data-flow analysis. An IDE's 'rename symbol' is a parser plus a symbol table with scopes. You have built the machinery; the applications differ mainly in what they do with the tree.
If you want to keep going, in order of return on effort
- Emit LLVM IR instead of MIPS. Two hundred lines, and your language suddenly runs natively on every machine LLVM targets — with LLVM's optimizer, which is rather better than yours.
- Build the flow graph and a liveness analysis. Then a real register allocator and global optimization both become possible, and you can measure the difference with the tools from Topic 4.
- Add a type system. Start with
boolandfloat. The work is almost entirely in phase 3, and it will show you why real compilers have a type system rather than a type field. - Write the ARM back end. You already know it is one file, and Topic 5 made you list which functions change.
11Self-check
Your optimizer reports 35% fewer TAC instructions but SPIM reports 4% fewer instructions executed. What do you write in the report?
Which of these is the best entry in a limitations section?
A phase takes 30% of your compiler's run time. You make it twice as fast. What is the overall improvement?
Why should errors detected in phase 4 or 5 be reported differently from errors in phases 1–3?
What is the strongest single claim you can make about your compiler's architecture?
12References
- Aho, Lam, Sethi & Ullman, 2nd ed. — §1.4 (the science of building a compiler), §1.5 (applications of compiler technology); §6.2.4 (static single-assignment form), §6.5 (type checking); §7.5 (garbage collection); §8.8 (register allocation and assignment, including graph coloring), §8.9 (instruction selection by tree rewriting); §9.1–9.3 (optimization and data-flow analysis); ch. 10 (instruction-level parallelism and scheduling); ch. 11 (parallelism and locality).
- Cooper & Torczon, Engineering a Compiler — a strong second text, more implementation-oriented, particularly on register allocation.
- Chaitin et al., Register allocation via coloring, Computer Languages 6, 1981 — the original graph-coloring paper.
- Cytron et al., Efficiently computing static single assignment form, ACM TOPLAS 13(4), 1991.
- The LLVM documentation on its intermediate representation, if you want to see a production IR up close.