The GATE Grind

GATE 2014 CS (CS3) – Question 44

Compiler Design · Code Optimization and Data Flow Analysis · 2 marks · Multiple choice

Basic block:

a = b + c
c = a + d
d = b + c
e = d - b
a = e + b

Find the minimum numbers of nodes and edges, respectively, in its DAG representation.

  1. 6 and 6
  2. 8 and 10
  3. 9 and 12
  4. 4 and 4

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) 6 and 6

Explanation

Use initial leavesb,c0,d0. Build n1=b+c0,n2=n1+d0,n3=b+n2. Updated c=n2,d=n3; algebraic cancellation gives e=n3−b=n2and final a=e+b=n3. There are3leaves plus3operator nodes and6operand edges, **6and6,A**. This minimum uses algebraic identities beyond structural common-subexpression elimination.