Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 61 ยท Intermediate Code and Optimization

Generating Three-Address Code

Learn to generate three-address code from an AST: temporaries, labels, lowering if and while, short-circuit booleans, and a runnable Python generator.

The previous lesson showed what three-address code looks like. Now we make it. A code generator for TAC is a tree walk much like the type checker, but instead of returning a type for each expression it emits instructions and returns the address where the result lives. The interesting part is not arithmetic, which is easy, but control flow: turning if, while, and and or into labels and jumps.

By the end of this lesson you will have a generator of about 100 lines for expressions, assignments, if/else, while, comparison, and, or and not, plus a cleanup pass and a small interpreter that proves the generated code does the same thing as the source.

Temporaries: one name per intermediate result

Each time the generator finishes an operator it creates a new temporary (t1, t2, ...) to hold the result and emits one instruction. The recursive function returns the name of the address holding the node's value. For a literal that is the number itself, for a variable it is the variable's name, and for an operator it is the fresh temporary.

The order of the walk matters. For a + b * c, the right child b * c must be emitted first, because the + instruction refers to its result. A post-order walk (children before parent) always produces instructions in a valid order.

Python Expressions into temporaries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

We borrow Python's own ast module to parse the source, as in what is a compiler; the generator would work the same way on your own AST. Look at (a + b) * (a - b): it needs three temporaries, the third combining the first two. Look also at the assignment x = 2 * (y + 3) - z: the generator ends with x = t3, a pointless copy, because it first computed the expression into a temporary. A smarter generator passes the destination down so the last operator writes into x directly; leaving the copy for local optimizations to remove is the simpler design.

Labels and jumps

Processors have no if and no while. They have a conditional jump (jump to an address if a test holds) and an unconditional jump. In TAC, an address in the code is given a name, a label, written L1:, and the jumps say goto L1 or if a < b goto L1.

Our TAC has these instruction forms:

TEXT
x = y op z          binary operation
x = y               copy
if a rel b goto L   conditional jump (rel is <, <=, >, >=, ==, !=)
goto L              unconditional jump
L:                  label (an address, not an instruction that does anything)
print x             output

Lowering if and while

The recipe for each statement is a fixed pattern with new labels. The generator allocates the labels first, emits the pieces in order, and places each label where its code begins.

flowchart TB
    subgraph IF["if cond: A else: B"]
      I0["jump to L_yes if cond,<br/>otherwise L_no"] --> I1["L_yes: code for A<br/>goto L_end"]
      I0 --> I2["L_no: code for B"]
      I1 --> I3["L_end:"]
      I2 --> I3
    end
    subgraph WHILE["while cond: body"]
      W0["L_begin: jump to L_body<br/>if cond, otherwise L_end"] --> W1["L_body: code for body<br/>goto L_begin"]
      W1 --> W0
      W0 --> W2["L_end:"]
    end

An if splits and rejoins; a while tests at the top and loops back with an unconditional jump.

A while loop re-tests the condition on every pass, so the label sits before the condition code and the body ends with a jump back to it. An if needs a jump over the else part at the end of the then part, or the program would run both.

Short-circuit booleans

In most languages a and b does not evaluate b when a is false, and a or b does not evaluate b when a is true. This is not only an optimization: x != 0 and y // x > 1 is a common idiom that relies on it to avoid dividing by zero.

The clean way to implement this is to compile a boolean expression not into a value but into jumps: given two labels, true_label and false_label, the generated code transfers control to one of them. Then:

  • A and B: test A; if false jump to false_label; otherwise fall into the code for B, which jumps to either label.
  • A or B: test A; if true jump to true_label; otherwise fall into the code for B.
  • not A: compile A with the two labels swapped. No instruction is needed at all.
  • A comparison a < b: emit if a < b goto true_label followed by goto false_label.

An if or while simply asks for jumping code with its own labels, so the conditions need never become 0 or 1. Only when a boolean appears in a value context (ok = x > 0 and y > 0) must the generator materialize it: jump code, then t = 1 on the true path and t = 0 on the false path.

The complete generator

Read this in three groups: value for arithmetic and boolean values, jumping for conditions, and statement for the control-flow patterns. After it come a cleanup pass, tidy, and a tiny interpreter, run_tac, so you can check that the generated code really computes the right answer.

Python A TAC generator for if, while, and, or, not

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study the first listing. The loop condition i <= 10 and not (total > 20) became two tests. The not swapped the labels, so if total > 20 goto L3 jumps out of the loop and goto L2 continues. The condition i % 2 == 0 or i == 7 is also two tests, and the second is skipped when the first succeeds (goto L5 straight to the then part). The naive output is full of patterns like if ... goto A followed by goto B followed by A:, which the tidy pass replaces with one flipped test (if i != 7 goto L6). That shrinks the listing from 26 to 19 lines and the run from 142 to 106 executed steps, with the same printed answer, 27: the loop adds 2, 4, 6, 7 (the i == 7 case) and 8, which makes 27, and at i = 9 the test total > 20 finally stops it.

The second program shows why short-circuit jumps matter. When x is 0, the first test jumps straight to L2 (t1 = 0), and the instruction t2 = y / x is never executed. If the generator had evaluated both sides eagerly, run_tac would raise a division-by-zero error.

Real compilers do this cleanup differently. They pass a fallthrough label into the jumping code so the generator emits only one jump where two were needed. The result is the same as tidy, and the "peephole" version here is easier to read and to extend.

What the generator guarantees (and what it ignores)

The generated code is correct but naive. Notice what it does not do:

  • It makes needless copies (t2 = total + i then total = t2).
  • It allocates a new temporary for every operator and never reuses them.
  • It does not notice that i % 2 == 0 could be tested in other ways.

That is on purpose. A generator that is only trying to be correct is simple to write and to trust. The improvements belong to optimization passes that work on the TAC afterwards, beginning with basic blocks and control flow graphs and local optimizations. Separating "generate" from "improve" is the standard compiler architecture.

Two practical notes for your own generator. First, number the labels and temporaries with counters stored on the generator object (as here), never in global variables, so you can compile two programs in one run. Second, write a TAC interpreter early (like run_tac): once you can run the output, a pile of test programs checks the generator by comparing its results with the source language's own answers.

Quadruples, triples and indirect triples

So far the generator wrote each instruction as text such as t3 = t1 - t2. Inside a compiler, an instruction is a record, and there are three classic ways to lay it out in memory. They all hold the same information; they differ in how an instruction refers to the result of another one.

Layout Fields How a result is named Moving an instruction
Quadruple op, arg1, arg2, result by a name (t1) stored in the result field easy: the names do not change
Triple op, arg1, arg2 by the row number of the instruction that computes it, written (1) hard: every reference to a moved row must be renumbered
Indirect triple a triple table plus a separate list of pointers giving the execution order by row number in the triple table easy: reorder the pointer list and leave the table alone

A quadruple spends one extra field, and often a symbol-table entry for every temporary, but it is position independent: an optimizer can delete, insert or reorder quadruples freely, as long as it respects the data dependencies. A triple saves the result field and the temporaries, but the row number is both the identity and the position of an instruction, so any reordering is a renumbering job. Indirect triples separate the two ideas: the triple's identity is its row in the table, and the program order is a different list. Optimizers that move code around a lot, such as local optimizations, or the schedulers in instruction scheduling, prefer quadruples or indirect triples. (Modern compilers such as LLVM go one step further: an instruction refers to the instruction object that computes its operand directly, like a triple that uses a pointer instead of a row number, which keeps reordering cheap.)

The program below stores x = (p + q) - p * q in all three layouts, then swaps the two independent instructions p + q and p * q, and checks the result of each version. The expected value is 10 - 21 = -11.

Python Three layouts, one reordering

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the last four lines. Swapping quadruples is harmless, because t3 = t1 - t2 still names its operands. Swapping triple rows without touching the references silently computes p * q - (p + q) and prints 11, the wrong sign. The fix is to renumber ((1) becomes (2) and the other way round), which is easy for two rows and tedious for a whole function. With indirect triples, the pointer list [2, 1, 3, 4] says "run row 2 first", the table does not change, and the answer is still -11.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the recursive function that generates TAC for an expression, what does it return?

    The caller needs to know where the value will be, so each call returns a name: a constant, a variable, or the fresh temporary it just assigned.
  2. 2. Why does a while loop's label come before the code that evaluates the condition?

    Looping means going back to the test. The unconditional jump at the end of the body targets the label placed ahead of the condition code.
  3. 3. How is not A handled when compiling a condition into jumping code?

    Swapping the labels reverses the outcome with zero extra instructions. If A would jump to 'true', now it jumps to 'false' and vice versa.
  4. 4. For x != 0 and y // x > 1, why must the generated code skip the division when x is 0?

    With jumping code, a false left operand jumps straight to the false label, so the instructions for the right operand are never executed.

Summary

  • Three-address code is stored as quadruples (named results, easy to reorder), triples (row-number references) or indirect triples (a pointer list over the triples).
  • A TAC generator is a post-order tree walk that emits one instruction per operator and returns the address holding each result.
  • if and while lower to fixed patterns of labels and jumps; a while loops back to a label placed before the condition.
  • Conditions are compiled into jumping code with a true label and a false label, which gives short-circuit and/or for free and makes not a label swap.
  • A boolean used as a value is materialized as 1 or 0 using the same jumps.
  • The raw output is correct but wasteful; a small peephole pass and later optimizations tidy it, and a TAC interpreter lets you test the generator.

Next: Basic Blocks and Control Flow Graphs