Consider the following C code segment: a = b + c; e = a + 1; d = b + c; f = d…
2021
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 _____________ .
Attempted by 16 students.
Show answer & explanation
Correct answer: 6
Answer: 6 nodes.
Explanation: In a DAG for this code we merge identical computations so that common subexpressions share nodes. Variable names are labels on nodes and do not create extra nodes by themselves.
b (leaf)
c (leaf)
b + c (shared by a and d)
constant 1
(b + c) + 1 (shared by e and f)
e + f which produces g
Counting these distinct nodes gives 6 in total.
A video solution is available for this question — log in and enroll to watch it.