Skip to content
CampusPrep
AD-604 (C) · Compiler Design/Quick Revision Short Notes

Compiler Design (AD-604 (C)) - Unit 4 Short Notes

How unit 4 is examined

This unit covers intermediate code, the code generator with basic blocks and flow graphs, and the last topic (register allocation, DAG, peephole), which carried all the marks in May 2024.

Intermediate code generation: Declarations, Assignment statements, Boolean expressions, Case statements, Back patching, Procedure calls

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Intermediate code is a machine-independent representation, usually three-address code with at most one operator and three addresses per instruction, produced by syntax-directed translation between the front end and the back end.</mark>

Key points.

  1. Declarations enter each name in the symbol table with its type and an offset, and the offset then grows by the type's width: offset = offset + width.
  2. An assignment id := E generates t1 = ... for the sub-expressions using newtemp(), then id.place = E.place.
  3. Boolean expressions are translated either as numerical values (1 or 0) or by flow of control with true and false jumps, which allows short-circuit evaluation.
  4. A case statement becomes a table of value-label pairs (or a jump table) tested in order, ending with a default label.
  5. Backpatching leaves jump targets blank and fills them later: makelist(i) creates a list, merge(p1,p2) joins two lists, and backpatch(p,i) sets label i in every listed jump, so one pass is enough.
  6. A procedure call is translated to param x1 ... param xn followed by call p, n, and the result of a function call is taken in a temporary.
  7. Three-address code is stored as quadruples (op, arg1, arg2, result), triples (no result field) or indirect triples (a list of pointers to triples).

Example. For a := b*-c + b*-c the code is t1 = minus c; t2 = b * t1; t3 = minus c; t4 = b * t3; t5 = t2 + t4; a = t5. For if a<b or c<d then S the flow-of-control code is if a<b goto Ltrue; goto L1; L1: if c<d goto Ltrue; goto Lfalse, and the backpatching lists fill Ltrue and Lfalse afterwards.

Code Generation: Issues in the design of code generator, Basic block and flow graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>The code generator maps the optimised intermediate code to correct and efficient target code; the code is divided into basic blocks, which are joined as a flow graph.</mark>

Key points.

  1. The design issues are the input form, the target program, instruction selection, register allocation, evaluation order and memory management.
  2. A basic block is a straight-line sequence with entry only at its first statement and exit only at its last, with no halt or branch inside.
  3. Leaders are the first statement, every jump target and every statement following a jump; a block runs from a leader up to the next leader.
  4. In the flow graph the nodes are basic blocks, and an edge from $B_1$ to $B_2$ means $B_2$ can follow $B_1$ by a jump or by falling through.
  5. Instruction selection chooses the cheapest target instruction sequence; a naive statement-by-statement translation gives redundant loads and stores, for example a = b + c then d = a + e loads a again.
  6. Register allocation is central because register operands are much faster than memory operands, and the number of registers is small.
  7. Evaluation order matters because some orders need fewer registers, and choosing the best order is itself NP-complete.

Example. For i = 1; L: t = i*4; i = i+1; if i<10 goto L; x = 0 the leaders are statement 1, L: t = i*4 (jump target) and x = 0 (follows a jump), so there are three blocks B1, B2, B3 with edges B1 to B2, B2 to B2 (loop) and B2 to B3.

Register allocation and assignment, DAG representation of basic blocks, peephole optimization, generating code from DAG

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A DAG of a basic block is a directed acyclic graph with one node per distinct value: leaves are the initial values of names, interior nodes are operators, and each node carries the names holding its value, so common subexpressions share one node.</mark>

Key points.

  1. Register allocation chooses which variables stay in registers at each point, and register assignment picks the actual register for each; the problem is NP-complete, so heuristics are used.

  2. Simple assignment keeps a register descriptor (what each register holds) and an address descriptor (where each variable's value is found), and loads an operand only when it is not already in a register.

  3. In graph colouring each variable is a node, an edge joins two variables that are live together, and the $k$ registers are the $k$ colours; if the graph cannot be $k$-coloured, a variable is spilled to memory.

  4. To build a DAG for x := y op z, find or create nodes for y and z, reuse an existing op node with the same children if there is one, otherwise create it, and attach x to that node.

  5. A DAG exposes common subexpressions, the values used outside the block, and which statements may be reordered.

  6. Code from a DAG is generated with children before parents, so each shared value is computed once and held in a register.

  7. Peephole optimization examines a small sliding window of target code and replaces it by a shorter or faster sequence; it is local, so it may need several passes.

  8. Peephole techniques are redundant load/store removal, unreachable code removal, flow-of-control (jump to jump) optimization, algebraic simplification, strength reduction and use of machine idioms.

  9. Generating code from a DAG follows the node listing algorithm: repeatedly select an unlisted interior node all of whose parents are listed, list it, then list its leftmost child if that is an unlisted interior node with all parents listed; the listing is then evaluated in reverse order, which reduces the registers needed and stores each shared value once.

  10. Getreg for x = y op z picks a register holding y if y is not live afterwards, else an empty register, else spills the least needed register; after the instruction the descriptors are updated.

  11. The DAG also allows dead code elimination, since a root with no live label can be dropped, and it supports algebraic laws such as reordering commutative operands to find more sharing.

Register allocation example. For the block t = a+b; u = t*c; v = u-a with two registers: MOV a,R0; ADD b,R0 (R0 holds t), MOV c,R1; MUL R0,R1 (R1 holds u and R0 is free because t is dead), SUB a,R1 (R1 holds v), then MOV R1,v. The descriptors change at each step, and only a is loaded twice because it is not kept in a register. In colouring terms, t and c are live together, so they interfere; t and v never coexist, so they can share one register, and two colours suffice.

Peephole techniques with examples.

Technique Before After
Redundant load/store MOV a,R0 then MOV R0,a MOV a,R0
Unreachable code goto L2; x = 1; L2: goto L2; L2: (statement removed)
Jump to jump goto L1 ... L1: goto L2 goto L2
Strength reduction x*2 or x*8 x<<1 or x<<3
Algebraic simplification x = x+0, x = x*1 removed
Machine idiom ADD #1,R0 INC R0

Benefits are a smaller and faster program at low cost, since the compiler needs only pattern matching; limits are that the window is local, so each pass may expose new patterns and the result is not globally optimal.

Example (May 2024 DAG). Block: D := B*C; E := A+B; B := B+C; A := E-D.

Statement Node made Labels
D := B*C n1 = *(B0, C0) D
E := A+B n2 = +(A0, B0) E
B := B+C n3 = +(B0, C0), new because it differs from n2 B
A := E-D n4 = -(n2, n1) A

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 484.2 320.8" width="484.2" height="320.8" role="img" aria-label="DAG. n1 = BC (D), n2 = A+B (E), n3 = B+C (B), n4 = E-D (A). Leaves A0, B0, C0 are initial values."><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M174.6,55.1 L113,135.2" marker-end="url(#ah7)"/><path class="e" d="M197.8,55.1 L259.4,135.2" marker-end="url(#ah7)"/><path class="e" d="M92.2,169 L48.9,261.8" marker-end="url(#ah7)"/><path class="e" d="M110.7,167.6 L174.6,263.3" marker-end="url(#ah7)"/><path class="e" d="M261.7,167.6 L197.8,263.3" marker-end="url(#ah7)"/><path class="e" d="M282.7,167.6 L346.6,263.3" marker-end="url(#ah7)"/><path class="e" d="M427.2,160.3 L205,271.4" marker-end="url(#ah7)"/><path class="e" d="M433.7,167.6 L369.8,263.3" marker-end="url(#ah7)"/><circle class="n" cx="186.2" cy="40" r="18"/><text class="t" x="186.2" y="40" dy=".35em" text-anchor="middle">n4</text><circle class="n" cx="100.2" cy="151.8" r="18"/><text class="t" x="100.2" y="151.8" dy=".35em" text-anchor="middle">n2</text><circle class="n" cx="272.2" cy="151.8" r="18"/><text class="t" x="272.2" y="151.8" dy=".35em" text-anchor="middle">n1</text><circle class="n" cx="444.2" cy="151.8" r="18"/><text class="t" x="444.2" y="151.8" dy=".35em" text-anchor="middle">n3</text><circle class="n" cx="40" cy="280.8" r="18"/><text class="t" x="40" y="280.8" dy=".35em" text-anchor="middle">A0</text><circle class="n" cx="186.2" cy="280.8" r="18"/><text class="t" x="186.2" y="280.8" dy=".35em" text-anchor="middle">B0</text><circle class="n" cx="358.2" cy="280.8" r="18"/><text class="t" x="358.2" y="280.8" dy=".35em" text-anchor="middle">C0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">DAG. n1 = BC (D), n2 = A+B (E), n3 = B+C (B), n4 = E-D (A). Leaves A0, B0, C0 are initial values.</figcaption></figure>

Code generated in two-address form (OP src, dst):

MOV B,R0 ; MUL C,R0     R0 = D
MOV A,R1 ; ADD B,R1     R1 = E
MOV B,R2 ; ADD C,R2     R2 = new B
SUB R0,R1 ; MOV R1,A    A = E - D

Peephole example. MOV a,R0 followed by MOV R0,a becomes MOV a,R0 because the store is redundant; x*2 becomes x<<1; goto L1 where L1: goto L2 becomes goto L2.

Answer frame.

  • DAG question: open by defining the DAG and common subexpression; draw the DAG above; develop the four construction steps and the label table; close with the final labels A, B, D, E.
  • Peephole question: open with the sliding-window definition; give techniques 1-5 each with a before/after line; close with the benefit (smaller, faster code) and the limit (local view only).
  • Register question: open by separating allocation from assignment; explain descriptors, then colouring and spilling with a small example; close with target machine constraints.

Pitfall: Reusing the B*C node for B := B+C, or hanging label B on the leaf B0, loses marks; the new B is a fresh + node.

Asked: [8 marks] (May 2024) What is DAG? Construct DAG for the basic block D := B*C; E := A+B; B := B+C; A := E-D. Asked: [6 marks] (May 2024) Explain about peephole optimization with example. Asked: [6 marks] (May 2024) Explain Register allocation and assignment with suitable example.

Last-minute revision

  • Three-address code has at most one operator and three addresses per instruction.
  • Backpatching uses makelist, merge and backpatch to fill jump labels in one pass.
  • Leaders are the first statement, jump targets and statements after jumps.
  • Flow graph nodes are basic blocks; edges are possible control transfers.
  • DAG leaves are initial values, interior nodes are operators, and a shared node is a common subexpression.
  • The May 2024 DAG has four operator nodes: *, + (A+B), + (B+C) and -.
  • Register allocation decides which values are in registers; assignment decides which register.
  • Spilling stores a variable in memory when the colours run out.
  • Peephole optimization works on a small window of target code.

Memory hooks

  • Leaders lead blocks: first, target, after-jump.
  • DAG: one value, one node.
  • Peephole is a keyhole view, so only local fixes.
  • Allocation is who gets a register; assignment is which register.

Coverage checklist

  • Intermediate code generation: Declarations, Assignment statements, Boolean expressions, Case statements, Back patching, Procedure calls (no past questions).
  • Code Generation: Issues in the design of code generator, Basic block and flow graphs (no past questions).
  • Register allocation and assignment, DAG representation of basic blocks, peephole optimization, generating code from DAG (May 2024: DAG 8 marks, peephole 6 marks, register allocation 6 marks).
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in