The Directed Acyclic Graph (DAG) is used to represent the structure of basic blocks, to visualize the flow of values between basic blocks, and to provide optimization techniques in the basic block. To apply an optimization technique to a basic block, a DAG is a three-address code that is generated as the result of an intermediate code generation.
Examples of directed acyclic graph:
A Directed Acyclic Graph for Basic Block is a directed acyclic graph with the following labels on nodes.
There are three possible scenarios for building a DAG on three address codes:
Case 1 – x = y op z
Case 2 – x = op y
Case 3 – x = y
Directed Acyclic Graph for the above cases can be built as follows :
Step 1
Step 2
Step 3
Remove x from the list of node identifiers. Step 2: Add x to the list of attached identifiers for node n.
Example :
T0 = a + b —Expression 1
T1 = T0 + c —-Expression 2
d = T0 + T1 —–Expression 3
Expression 1 : T0 = a + b
Expression 2: T1 = T0 + c
Expression 3: d = T0 + T1
Final Directed acyclic graph
Example :
T1 = a + b
T2 = T1 + c
T3 = T1 x T2
Example :
T1 = a + b
T2 = a – b
T3 = T1 * T2
T4 = T1 – T3
T5 = T4 + T3
Example :
a = b x c
d = b
e = d x c
b = e
f = b + c
g = f + d
Final Directed acyclic graph
Example :
T1: = 4*I0
T2: = a[T1]
T3: = 4*I0
T4: = b[T3]
T5: = T2 * T4
T6: = prod + T5
prod: = T6
T7: = I0 + 1
I0: = T7
if I0 < = 20 goto 1
Final Directed acyclic graph
26 videos|66 docs|30 tests
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|