construct a DAG for a+a*b-c+b-c*d
Answers
Answer:
Directed Acyclic Graph :
The Directed Acyclic Graph (DAG) represents the structure of basic blocks, which visualizes the flow of values between basic blocks and the provided optimization techniques in the basic block. To apply an optimal technique to a basic blocks, a DAG is a three-addressed code that is generated as a result of an intermediate code generations.
Directed acyclic graph is a type of data structure those are used to apply transformation to basic blocks.
The Directed Acyclic Graph (DAG) facilitated the transformations of basic blocks.
DAG is an efficient method for identifying common sub-expressions.
It demonstrates how the statement’s computed value is used in subsequent statements.
#SPJ2
Answer:
Directed acyclic graph for the expression a+a*(b-c)+(b-c)*d.
Explanation:
STEPS FOR CONSTRUCTING A DAG:
1.d1=leaf(id,entry-a)
2.d2=leaf(id,entry-a)=d1
3.d3=leaf(id,entry-b)
4.d4=leaf(id,entry-c)
5.d5=node('-',d3,d4)
6.d6=node('*',d1,d5)
7.d7=node('+',d1,d6)
8.d8=leaf(id,entry-b)=d3
9.d9=leaf(id,entry-c)=d4
10.d10=node('-',d3,d4)=d5
11.d11=leaf(id,entry-d)
12.d12=node('*',d5,d11)
13.d13=node('+',d7,d12)
