GATE CSE 2021 Set 1 Q60: Number of nodes in the DAG of a basic block

Consider the following C code segment:

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

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

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 6 (official GATE 2021 final answer key)

Concept used: A DAG shares common subexpressions: identical operator nodes with identical children are created once.

First step: Note that d = b + c repeats a, and so f = d + 1 repeats e; count leaves (b, c, 1) and the distinct interior nodes.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key