search
Log In
49 votes
11.4k views

Consider the basic block given below. 

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

The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

  1. $6$ and $6$
  2. $8$ and $10$
  3. $9$ and $12$
  4. $4$ and $4$
in Compiler Design
edited by
11.4k views
0
Notice - No node no node for '=' operator
18

...............................

0
THIS IS IN SYLLABUS?
0
Yeah it is in syllabus. Question can be asked from anywhere if it is even a little bit in syllabus. So leave recent out of syllabus topics carefully.

5 Answers

57 votes
 
Best answer

A normal DAG construction will give $8$ nodes and $10$ edges as shown below.

Since, this question asks for minimum possible, we can assume algebraic simplification is allowed. So, $d = b + c, e = d - b$; can be simplified to $d = b + c$; $e = c$; Similarly, $e = d - b$; $a = e + b$; can be simplified to $a = d$. This gives the following DAG with $6$ nodes and $6$ edges.

https://cs.nyu.edu/~gottlieb/courses/2000s/2006-07-fall/compilers/lectures/lecture-14.html [working link]

Correct Answer: $A$


edited by
1
Why is definition d added to node a? In 3rd statement c is getting redefined and hence the new value of c would be used for defining d. Hence a new node for d is created. What am I missing, Arjun Sir?
0
Sorry. It was a mistake. I have corrected it now.
2
sir. the lnk is dead i need to study DAG . plz provide a gud link .
0
thanx arjun sir
0
@Arjun Sir, The link here is not working,have any alternative?
2
Is DAG in syllabus?  but can questions of this type be expected anyone reply.... Isn't DAG used for optimisation?
0
is this in syllabus???
0
yes. it's in syllabus.
0
@Arjun Sir

In 2nd Figure am unable to find edge of  e = d-b; except this am understand ...I think 7 edges will be there?plzz look if you have time?
0
but code optimization is not, then how is it in syllabus? :(
0
what sort of question can we expect with dag because it involves code optimization techniques which are nt in syllabus?
0
@sushmita

I think it is intermediate code and DAG combination question and both of them are in syllabus..
4
can we do it like this-

a=b+c

c=a+d

d=b+c

e=d-b

a=e+b

Now d is common subexpression so we need not compute it again-

Hence it will become-

a=b+c

c=a+d

e=a-b

a=e+b=a-b+b=a -----> redundant

Finally it becomes-

a=b+c

c=a+d

e=a-b

It will also require 6 nodes and 6 edges.
66

isn't it right?

0
It is also correct!!!
12

...........

0
Where is the assingment operator?
0
Had minimum not been asked, would be then go with 8 and 10 option?
0
@prayas

It is not required  because in DAG x:=y type of assignments need not to be performed (not required) untill and unless it is used for computation of further expression.
0

@shefali1

@sushmita

will ​​​​​@shefali1 method will always give correct result??

because it seems bit easy draw  DAG from reverse.

4 votes

Best approach of doing this question is "Go in reverse order". and it has asked for minimum so we can simplify wherever possible.

A = (E+B)

((D-B)+B) = (D) Because both + , - has same precedence

(B+C)

(B+(A+D))

(B+((B+C)+D))

 

0

@Nitesh Singh 2

How you put the bracket?

0
Brackets are just to indicate "appropriate value has been substituted in place of the previous variable".
3 votes

Simplifying the given equations : 
 
d = b + c (given) e = d – b (given) => d = b + c and e = c 
 
e = d - b (given) a = e + b (given) => a = d 
 
2014-set3-44 
 
Thus, the given DAG has 6 nodes and 6 edges. 

–3 votes
option B
–4 votes
answer - B
Answer:

Related questions

39 votes
6 answers
1
6.8k views
The minimum number of arithmetic operations required to evaluate the polynomial $P(X) = X^5+4X^3+6X+5$ for a given value of $X$, using only one temporary variable is ______.
asked Sep 28, 2014 in Compiler Design jothee 6.8k views
31 votes
3 answers
2
4.5k views
Which of the following statements are CORRECT? Static allocation of all data areas by a compiler makes it impossible to implement recursion. Automatic garbage collection is essential to implement recursion. Dynamic allocation of activation records is essential to implement recursion. Both heap and stack are essential to ... . $1$ and $2$ only $2$ and $3$ only $3$ and $4$ only $1$ and $3$ only
asked Sep 28, 2014 in Compiler Design jothee 4.5k views
22 votes
2 answers
3
3.4k views
Which one of the following is FALSE? A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end. Available expression analysis can be used for common subexpression elimination. Live variable analysis can be used for dead code elimination. $x=4*5 \Rightarrow x=20$ is an example of common subexpression elimination.
asked Sep 26, 2014 in Compiler Design jothee 3.4k views
22 votes
3 answers
4
3.3k views
One of the purposes of using intermediate code in compilers is to make parsing and semantic analysis simpler. improve error recovery and error reporting. increase the chances of reusing the machine-independent code optimizer in other compilers. improve the register allocation.
asked Sep 28, 2014 in Compiler Design jothee 3.3k views
...