Temporaries in TAC, registers in code generation

A compiler handles storage for intermediate values twice. The TAC generator decides which names hold intermediate values. The code generator then decides which machine registers hold those names at each moment. The two allocators solve the same problem at different levels, and this page walks through both using the algorithms in this course's compiler (tac.c and codegen.c).

The big picture

Take x = (a + b) * (c - d). The source never names a + b, but the machine has to keep that value somewhere while it computes c - d. That produces two separate questions:

1 · Allocating temporaries during TAC generation

The naive version and why it wastes space

newTemp() simply counts: t0, t1, t2, …, and every expression node gets a fresh name forever. It is correct but wasteful. A program with 500 additions needs 500 temporaries, and layoutFrame() gives each one its own 4-byte stack slot, even though only two or three are ever alive at the same moment.

The key observation: an expression temporary is used exactly once

A temporary created for an interior node of an expression tree is read by exactly one instruction, the one for its parent node. Once that instruction has been emitted, nothing later can refer to the temporary, so its name can be reused. Temps therefore behave like a stack: they are born in post-order and die as soon as their parent consumes them.

Data structure (tac.h)

typedef struct {
    int allocated[MAX_TEMPS];   /* allocated[n] == 1  ⇔  tn is live right now      */
    int maxUsed;                /* high-water mark: t0 … t(maxUsed-1) exist       */
    int freeList[MAX_TEMPS];    /* a STACK of dead temp numbers ready for reuse   */
    int freeCount;              /* stack pointer                                  */
} TempAllocator;

The algorithm

allocTemp():
  if freeCount > 0:
      n ← freeList[--freeCount]  // reuse (LIFO)
  else:
      n ← maxUsed++              // mint a new one
  allocated[n] ← 1
  return "t" + n

freeTemp(name):
  if name is not a temp: return   // "a", "42"
  n ← number in name
  if !allocated[n]: return        // double free
  allocated[n] ← 0
  freeList[freeCount++] ← n

/* generateTACExpr, NODE_BINOP */
left  = generateTACExpr(node->left);
right = generateTACExpr(node->right);

temp  = allocTemp();          /* ① result name   */
appendTAC(op, left, right, temp); /* ② consume both  */

freeTemp(left);                /* ③ children die  */
freeTemp(right);
return temp;                    /* parent frees it */

/* statements free the final result */
appendTAC(ASSIGN, expr, x);
freeTemp(expr);

1. Recurse first. Generate both children (post-order). Each child returns the name holding its value: a literal, a user variable, or a temp.
2. Allocate the result with allocTemp(). It takes a dead name from the top of the free stack if there is one, and otherwise mints a new name.
3. Emit the instruction. This is the only use of the children's values.
4. Free the children. freeTemp ignores anything that is not a temp, so it is safe to call on a or 42.
5. Return the result name to the parent, which is responsible for freeing it. At the top of the tree, the statement (assignment or print) frees it.

Worked trace: x = (a + b) * (c - d), then y = x + a

Two statements, four temp definitions, three names. However long the program gets, the number of names stays at the largest number of temps alive at one time, which depends on the shape of the biggest expression rather than on program length.

2 · Allocating registers during code generation

TAC now uses a small set of names: user variables plus a few temps. MIPS offers ten caller-saved scratch registers, $t0–$t9. The course compiler treats them as a write-back cache over memory, the same way a CPU cache sits in front of RAM.

Step 0 — every name gets a memory home first

Before emitting any instruction for a function, layoutFrame() walks its TAC and gives every declared variable and every temporary a slot in the activation record (reserveTemp). This is what makes spilling always possible: any register can be evicted at any moment, because its value always has somewhere to go.

This is also where Part 1 pays off. Fewer distinct temp names mean fewer slots and a smaller frame.

The register descriptor

The allocation algorithm — getReg(name, hasHome, load)

1. Hit? If some register already holds name, refresh its timestamp and return it. No instruction is emitted.
2. Free register? Take the first register with inUse == 0.
3. Otherwise evict. selectVictimReg() prefers a register whose value has no home (a literal, which can be re-created with li). Failing that, it picks the least recently used register.
4. Spill if needed. If the victim is dirty and has a home, emit sw to write it back. A clean victim needs no store because memory already matches.
5. Claim it. Record the new name and timestamp, and set dirty = 0.
6. Load if asked. If load is set, emit lw from the name's home.

Three wrappers pick the right flags for each role an operand can play:

Instruction selection then becomes almost mechanical:

case TAC_ADD: case TAC_SUB: case TAC_MUL: case TAC_DIV: {
    int a = operandReg(i->arg1);     /* read  → maybe lw / li        */
    int b = operandReg(i->arg2);     /* read  → maybe lw / li        */
    int d = defReg(i->result);      /* write → no load, mark dirty  */
    emit("add $t%d, $t%d, $t%d", d, a, b);
}

Deallocation — when registers are released

Nothing in this allocator releases a register at a name's last use. Registers are given up in only three ways:

• Eviction (on demand). The LRU victim is spilled if dirty, then reassigned.
• flushRegisters() before a jal (the callee may overwrite $t0–$t9), before every label (control can arrive from elsewhere with different cache contents), and at the end of the function. Every dirty value with a home is written back, then the whole cache is forgotten.
• End of function. initRegAlloc() resets the cache for the next function.

3 · Interactive lab

Write straight-line code: name = expr or print(expr), with + - * /, parentheses and unary minus. Step through phase 1 to watch temp names get recycled, then phase 2 to watch those names move between registers and memory. Every variable starts in memory with the value shown. The lab runs the emitted MIPS and compares its output with the value the source code should produce.

4 · Pitfalls — two bugs found (and fixed) in the course compiler

Both bugs reproduced on the Topic 6 compiler, and every topic shared the same functions. They are now fixed in .tools/master and every generated topic folder. The lab can still switch the old behavior back on. They make good exercises, because each one follows directly from breaking one of the rules above.

Pitfall 1 · freeTemp frees a live temp when a variable name starts with “t”

void freeTemp(char* temp) {
    if (!temp || temp[0] != 't') return;     /* "total" passes this test …   */
    int tempNum = atoi(temp + 1);              /* … and atoi("otal") == 0      */
    if (!tempAlloc.allocated[tempNum]) return;
    tempAlloc.allocated[tempNum] = 0;          /* t0 freed while still live!  */
    ...

freeTemp is called on every operand, and the check that is supposed to skip user variables accepts total, tax, temp, and so on. If t0 is live at that moment, it goes back on the free stack, the next allocTemp() hands it out again, and a value that is still needed gets overwritten:

// print(((a+b) * (total+c)) + ((d+e) * (f+g)))    a..g = 1..7, total = 100
t0 = a + b
t1 = total + c        ← freeTemp("total") releases t0 here
t0 = t0 * t1          ← allocTemp() hands t0 out again
t1 = d + e
t0 = f + g            ← overwrites (a+b)*(total+c) before it is used
t2 = t1 * t0
t0 = t0 + t2
PRINT t0              spim prints 130 — expected 426. Rename total → sum: 426.

Fix (applied): check the full shape of a temp name, the same test codegen.c’s isTemp() uses:

static int isTempName(const char* s) {
    if (!s || s[0] != 't' || !s[1]) return 0;
    for (int i = 1; s[i]; i++) if (s[i] < '0' || s[i] > '9') return 0;
    return 1;
}
void freeTemp(char* temp) {
    if (!isTempName(temp)) return;
    int tempNum = atoi(temp + 1);
    if (tempNum >= MAX_TEMPS || !tempAlloc.allocated[tempNum]) return;
    ...

Try it in the lab: load the “total” bug preset and toggle the first option.

Pitfall 2 · loading the second operand can evict the first

For d = a op b the code generator calls operandReg(arg1) and then operandReg(arg2). If the second call finds no free register, it asks selectVictimReg(), which returns the first register holding a homeless value. The literal that the first call just loaded is homeless, so it can be chosen. Both operands then end up in the same register:

// y = ((9 + 6) - r) * ((r * 2) * (9 * p))   p=3, r=7   (Topic 6, NUM_TEMP_REGS = 3)
    li   $t2, 9               ← operandReg("9")
    lw   $t2, 0($sp)   # p    ← operandReg("p") evicts the 9 it just loaded
    mul  $t0, $t2, $t2        ← computes p*p instead of 9*p
// spim prints 1008 — expected 3024.  13 of 150 random expressions went wrong.

With 10 registers this needs a full cache, so small tests pass, but large functions trigger it. The same hazard also hit array stores (the value in a register could be evicted by the base address), array addressing (the base could be evicted by the index), and &&/||. In the logical case defReg could also take a scratch register that releaseReg then wiped, losing the result. Rule: every register handed out while translating one TAC instruction is pinned until the next instruction begins. The fix went into the allocator itself instead of each call site, so no instruction case can forget it:

static int pinned[NUM_TEMP_REGS];   /* 1 = in use by the current instruction */

/* findVarReg (on a hit) and getReg (on a claim) both set pinned[r] = 1;
 * releaseReg clears it; the translation loop calls unpinAll() before
 * each TAC instruction. */

static int selectVictimReg(void) {
    int victim = -1;
    for (int i = 0; i < NUM_TEMP_REGS; i++) {       /* note: start at 0 */
        if (pinned[i]) continue;            /* the current instruction needs it */
        if (!regAlloc.regs[i].hasHome && regAlloc.regs[i].inUse) return i;
        if (victim < 0 || regAlloc.regs[i].lastUsed < regAlloc.regs[victim].lastUsed)
            victim = i;
    }
    if (victim < 0) { /* internal error: one instruction needs > 10 registers */ exit(1); }
    return victim;
}

Verified after the fix: all 55 test runs across topics 2–6 give identical output, and with NUM_TEMP_REGS reduced to 3 the random expressions that failed before (13 of 150) now all pass. The lab reproduces the old behavior: load the operand clobber preset with 3 registers and uncheck “Pin operands”. (The lab lets the destination reuse an operand’s register. The compiler pins that too, which is simpler and costs at most one extra register.)

Cheat sheet