GATE CSE 2021 Set 1 | Question: 50

Question

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 $\text{(DAG)}$. The number of nodes in the $\text{DAG}$ is _____________

Comments

A DAG representation can be constructed during the intermediate code generation phase of the compiler, and common sub-expression elimination inherently becomes possible if we were to use quad representation of the DAG, and assign new rows if and only if the required entry wasn’t found during a linear scan of the array containing the quads corresponding to the DAG. This way, it’s possible to determine that variables \(a\) and \(d\) represent the same value. But, I can’t seem to understand how \(e\) and \(f\) can be determined to be the same, unless we were to perform some code optimization on the DAG. The questions simply asks for the number of nodes in the DAG, without stating whether or not any code optimization was performed on the DAG. Then, why does the answer presume an application of code optimization on the DAG?

Answer 1

Here  $a$ and $d$ are same as both add same values $(bc)$ (common sub-expression elimination)

Since $a$ and $d$ are same $f$ and $e$ are also same as they compute $a+1$ and $d+1$ respectively.

• $a = d =b+c$
• $e = f = a+1$
• $g = e + e$ ($f$ and $e$ being same) 

So total no of nodes is $6$ $( a, b, c, e, 1,g)$

Ans $:6$ nodes

Comments

@Ankur29 A DAG representation can be constructed during the intermediate code generation phase of the compiler, and common sub-expression elimination inherently becomes possible if we were to use quad representation of the DAG, and assign new rows if and only if the required entry wasn’t found during a linear scan of the array containing the quads corresponding to the DAG. This way, it’s possible to determine that variables \(a\) and \(d\) represent the same value. But, I can’t seem to understand how \(e\) and \(f\) can be determined to be the same, unless we were to perform some code optimization on the DAG. The questions simply asks for the number of nodes in the DAG, without stating whether or not any code optimization was performed on the same. Then, why does the answer presume an application of some code optimization on the DAG?

Answer 2

the given c code can be written as:
a=b+c
e=a+1 =b+c+1
d=b+c
f=d+1 =b+c+1
g=e+f=(b+c+1)+(b+c+1)

Syntax tree of  $g=(b+c+1)+(b+c+1)$ is:

Since DAG  reused common sub-expression so redundant part is eliminated and join by single edges.

So number of nodes in dag are $6$ that are $(b,c,1,+,+,+)$ .

Answer 3

 

Total Nodes : 6 

Total Edges : 6 

 

Answer 4

Another way:

a=b+c

e=a+1

d=b+c

f=d+1

g=e+f

Now, g=e+f= e+d+1=e+b+c+1 = a+1+b+c+1 = b+c+1+c+b+1 = 2(b+1+c)

now

See this link https://drive.google.com/file/d/1wjXG98mSo2EckXaY-a0WbpgFvzqSfWqz/view?usp=sharing

We need 6 vertices and 6 edges