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:

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

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

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

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:

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

Emit the TAC before all targets are known:

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:

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.

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:

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

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.