Intermediate Code Generation Across Compiler Concepts: Worked TAC, Quadruples and DAG Optimisation

A cross-concept intermediate-code question rarely stops at a definition. You may have to preserve expression semantics, generate three-address code, change it into quadruples or triples, identify a basic block and decide whether a repeated expression is reusable. Cross-concept questions span several phases, so solve them in dependency order. With a=9, b=4, c=2 and d=3, the naive and optimised forms both give x=30; after redefining a, the second subtraction becomes 6 and reuse becomes invalid. Place the method within the broader CS Fundamentals map as you study.

Intermediate code generation: put the connected concepts in order

A textbook lowering proceeds from source expression to parse tree or abstract syntax tree (AST), syntax-directed translation, three-address code (TAC), quadruple or triple records, a basic-block DAG, and locally optimised TAC. Production compilers may use different IRs and pass orders.

One invariant holds: representation may change, but source-program value and side effects must not. TAC usually keeps one main operator on the right-hand side, with temporaries making order explicit. Keep three ideas separate. TAC is an instruction-like IR. Quadruples and triples are its record layouts. A directed acyclic graph, or DAG, can expose repeated computations inside one basic block. These ideas connect the surrounding phases of Compiler Design.

TAC, quadruples and triples: fix the notation before solving

The needed TAC forms are x = y op z, x = op y, x = y, and a final assignment such as x = t3 + t1. Preserve explicit parentheses. Do not reassociate arithmetic unless permitted.

A quadruple is (op, arg1, arg2, result), so t1 = a - b becomes (-, a, b, t1). A triple is (op, arg1, arg2), with its row position naming the result. Row 0: (-, a, b) is later referenced as (0). Here, the final triple store is (=, (4), x).

Quadruple results are named and easy to inspect. Triple operands point to row positions and avoid temporary names. Neither layout is universally better. The broader Intermediate Code Generation in Compiler Design: Three-Address Code, Quadruples, Triples and Worked Examples connects IR purpose, unary-minus lowering, control flow and DAG counting. The narrower question is whether one six-instruction run-time trace can become four without changing x, and exactly which redefinition makes that reuse illegal.

Worked example: generate and evaluate the naive TAC

Use this source statement and run-time test data:

x = (a - b) * (c + d) + (a - b)
a = 9, b = 4, c = 2, d = 3

Treat this as one basic block. Assume the scalar operands remain unchanged and arithmetic has no side effects. The values are test inputs, not compile-time constants.

Generate unoptimised TAC in source-tree order:

t1 = a - b
t2 = c + d
t3 = t1 * t2
t4 = a - b
t5 = t3 + t4
x  = t5

Trace every instruction:

Rows t1 and t4 compute the same ordered expression from unchanged operands, which matters when building the DAG.

Encode the same TAC as quadruples and triples

The TAC becomes these quadruples:

Triples use row positions as results:

Quadruple row 2 reads t1 and t2. Triple row 2 reads positions (0) and (1). Both calculate the subtraction twice and store x=30. Count names and records separately: naive quadruples name five temporaries in six records. Triples have no t1-style names but still have six records.

Use a basic-block DAG to remove the repeated expression

Use leaves a=9, b=4, c=2, d=3; n1=-(a,b)=5; n2=+(c,d)=5; n3=*(n1,n2)=25; and root n4=+(n3,n1)=30, labelled x. The second a-b points to n1 instead of creating another node.

Reuse is valid because the operator and ordered operands match, a and b remain unchanged, and evaluation has no side effect. Textual repetition alone is insufficient.

The optimised TAC and quadruples are:

t1 = a - b             0  (-, a,  b,  t1)
t2 = c + d             1  (+, c,  d,  t2)
t3 = t1 * t2           2  (*, t1, t2, t3)
x  = t3 + t1           3  (+, t3, t1, x)

Evaluation gives 5, 5, 25, then 30. Six naive instructions become four, a reduction of two for this example only. The test inputs verify equal semantics. A compiler cannot replace the expression with 30 unless those values are compile-time constants.

Cross-concept traps: know when the shortcut breaks

Do not treat test values as constants. Replacing the expression with 30 is wrong for run-time inputs. Use them only to check both IR forms.

Test “operands unchanged” with a redefinition:

t1 = a - b
a = a + 1
t2 = a - b

Starting at a=9, b=4, t1=5. Then a=10, so t2=10-4=6, not 5. Reuse is invalid.

Also preserve explicit parentheses, do not read triple position (0) as numeric zero, and do not equate fewer triple names with fewer computations. Both naive layouts have six records and two subtractions.

A local DAG alone cannot justify reuse across an unknown call, volatile read or control-flow boundary. Operand validity must still be established.

How cross-concept intermediate-code questions test understanding

Question forms include generating TAC, translating it into quadruples or triples, evaluating the stated test values, counting records and temporaries separately, detecting common subexpressions, and testing whether a redefinition blocks reuse.

Check that you can answer these five points without looking back:

1. The naive result is x=30.

2. Naive TAC has six instructions and five named temporaries.

3. Optimised TAC has four instructions.

4. DAG node n1 is reusable because a and b stay unchanged.

5. After redefining a, the second a-b is 6, not 5.

For a record-focused comparison that includes indirect triples and pointer reordering, use Three-Address Code (3AC): Quadruples, Triples and Indirect Triples with a Worked Example. That five-record expression answers reordering questions; the six-to-four trace above answers DAG-equivalence and redefinition questions.

Intermediate code generation across concepts: short version and next step

Preserve source semantics, lower one operation at a time into TAC, choose a record layout, build a basic-block DAG, and reuse a node only while its operands remain valid. Verify the result against the original: with a=9, b=4, c=2, d=3, both versions give x=30. Redraw both diagrams and regenerate the four-row optimised table from a blank page. Use ZERO TO HERO (Complete Course) for the broader Compiler Design sequence, then GATE Guidance by Sanchit Sir for wider structured preparation.