Intermediate Code Generation in Compiler Design: TAC, Backpatching and DAGs

Connect expressions, short-circuit control flow and local optimisation through a single worked translation, from source code to resolved TAC and a reusable DAG.

KnowledgeGate Team

Exam prep & CS education

Updated 30 Oct 20265 min read
Intermediate Code Generation in Compiler Design: TAC, Backpatching and DAGs

Intermediate-code questions become hard when expressions, Boolean short-circuiting, backpatching and local DAG reuse interact. For broad IR forms and temporary counting, use Intermediate Code Generation: TAC, Quadruples, Triples; for record layouts and indirect triples, use Three-Address Code (3AC): Quadruples, Triples and Indirect Triples with a Worked Example; for straight-line TAC-to-DAG equivalence, use Intermediate Code Generation Across Compiler Concepts: Worked TAC, Quadruples and DAG Optimisation. The decisive path here is different: one Boolean fragment is backpatched from unresolved jumps to exact targets, followed by a separate local-DAG safety check. Preserving meaning requires explicit evaluation order and control flow.

What intermediate code generation must preserve

Intermediate code connects the front end to target-code generation:

source program -> tokens and syntax tree -> semantic information -> intermediate representation -> optimisation -> target code

This machine-independent IR must preserve evaluation order, types, conversions, side effects and branches.

Three-address code, or TAC, has at most one right-hand-side operator. Its forms include x = y op z, x = op y, x = y, if x relop y goto L, goto L, param x, call p, n and return y.

Syntax determines grouping, semantic analysis supplies types and conversions, and short-circuit rules create control flow. Backpatching fills unknown targets. A DAG exposes repeated work in a basic block.

TAC, quadruples and triples: fix the branch-body notation

The selected branch contains x = (a + b) * (c - d). Before adding its jumps, translate that arithmetic into TAC:

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

Temporaries expose precedence and order. Quadruples store (op, arg1, arg2, result):

op

arg1

arg2

result

+

a

b

t1

-

c

d

t2

*

t1

t2

t3

=

t3

-

x

Triples identify results by row index. For =, arg1 is source and arg2 destination.

index

op

arg1

arg2

0

+

a

b

1

-

c

d

2

*

(0)

(1)

3

=

(2)

x

Both show the same work. Quadruples name results and are easier to reorder. Triples use positions, so moving a row can force updates. Neither is universally better.

Worked example: translate and evaluate the complete source fragment

Use this source and these values:

Code
a = 4, b = 9, c = 3, d = 1

if (a < b && c != 0)
    x = (a + b) * (c - d);
else
    x = a - d;

Both 4 < 9 and 3 != 0 are true. Then t1 = 4 + 9 = 13, t2 = 3 - 1 = 2, and t3 = 13 * 2 = 26. Thus x = 26.

The unselected else value is 4 - 1 = 3, so it is not assigned.

Do not flatten && into an eager arithmetic temporary. Its second test follows the first true edge, while either false edge reaches else.

Backpatch the Boolean control flow step by step

Resolved TAC control-flow graph shows Boolean backpatching and the true route ending with x = 26.

Emit the TAC before all targets are known:

Code
1: if a < b goto _
2: goto _
3: if c != 0 goto _
4: goto _
5: t1 = a + b
6: t2 = c - d
7: t3 = t1 * t2
8: x = t3
9: goto _
10: t4 = a - d
11: x = t4
12: next statement

For a < b, truelist = {1} and falselist = {2}. Marker M = 3 starts test two, so patch {1} to 3. For c != 0, truelist = {3} and falselist = {4}. The whole && has true list {3} and merged false list {2, 4}.

Patch {3} to then at 5, {2, 4} to else at 10, and {9} to exit 12. The resolved TAC is:

Code
1: if a < b goto 3
2: goto 10
3: if c != 0 goto 5
4: goto 10
5: t1 = a + b
6: t2 = c - d
7: t3 = t1 * t2
8: x = t3
9: goto 12
10: t4 = a - d
11: x = t4
12: next statement

The route 1 -> 3 -> 5 -> 6 -> 7 -> 8 -> 9 -> 12 ends with x = 26.

Control-flow diagram for a=4, b=9, c=3, d=1: both tests true, so lines 5-9 give x=26 before joining line 12.

Build a DAG to remove repeated work inside one basic block

In a separate basic block, set p = 6, q = 4 and r = 5, then compute u = p * q, v = p * q and w = (p * q) + r. Since p * q = 6 * 4 = 24, u = 24, v = 24 and w = 24 + 5 = 29.

Leaves are p=6, q=4 and r=5. The multiplication node n1 has children p and q, value 24, and names u and v. The addition node n2 has children n1 and r, value 29, and name w. All three product occurrences share n1.

The cleaned TAC is:

Code
t1 = p * q
u = t1
v = t1
t2 = t1 + r
w = t2

Multiplications fall from three to one while u=24, v=24 and w=29 remain. This applies only in this block with unchanged operands.

Cross-concept traps and how questions expose them

Trap

Why it fails

Correct check

Worked-example evidence

Ignoring precedence

Grouping changes

Read the syntax grouping first

A sum and a difference feed multiplication

Treating && eagerly

Short-circuit flow is lost

Follow both edges

Line 3 follows line 1's true edge only

Confusing a temporary with a triple index

Positions are not names

Read (i) as row i's result

(0) and (1) feed row 2

Patching one false list

A false route stays wrong

Merge false lists

{2, 4} both target line 10

Merging nodes after an operand changes

Values can differ

Require unchanged operands

p and q stay fixed

Use one check for each common question form:

  • Count TAC statements or temporaries: expand one right-hand-side operator at a time.

  • Choose a quadruple: track its result column.

  • Follow a triple: resolve the referenced row.

  • Fill targets: retain both lists until blocks are known.

  • Identify leaders and basic blocks: mark targets and statements after jumps.

  • Detect a shared DAG node: require matching operators, operands and no redefinition.

Intermediate code generation: the short version and next step

Preserve the source meaning, split compound expressions into TAC, choose a representation, make Boolean control flow explicit, backpatch unknown labels, and then use a basic-block DAG to spot safe reuse. Reproduce the resolved 12-line TAC and redraw the small DAG without looking. Your exact checks are x=26, unselected else value 3, targets 1->3, 2->10, 3->5, 4->10, 9->12, and one computation of p*q in the DAG. If you can reconstruct both without checking the answer, the representations have become one method rather than isolated definitions. For a sequenced Compiler Design route, use GATE Guidance by Sanchit Sir. For the broader learning path, see GATE CS Exam Preparation.