The GATE Grind

GATE 2021 CS (CS1) – Question 60

Compiler Design · Code Optimization and Data Flow Analysis · 2 marks · Numerical answer

Consider the following C code segment:

a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;

In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is ______.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 6

Explanation

Build the DAG: identical sub-expressions share one node.

Leaves (operands): $b$, $c$ and the constant $1$ (3 nodes).

Internal nodes:
1. $b+c$ — computed once and **shared** by `a = b+c` and `d = b+c`.
2. $(b+c)+1$ — shared by `e = a+1` and `f = d+1` (since $a$ and $d$ are the same node).
3. $e+f$ — node for `g`, whose two children are the same node, so it is a node with both edges going to the shared node.

Total nodes $=3+3=\mathbf6$.

More Code Optimization and Data Flow Analysis questions

All Code Optimization and Data Flow Analysis questions →