Data-flow Analysis - Theoretical Foundations - Part 1 Notes | EduRev

Created by: Shifali Jain

: Data-flow Analysis - Theoretical Foundations - Part 1 Notes | EduRev

 Page 1


Data-?ow Analysis: Theoretical Foundations -
Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Theoretical Foundations of DFA
Page 2


Data-?ow Analysis: Theoretical Foundations -
Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Theoretical Foundations of DFA
Foundations of Data-?ow Analysis
Basic questions to be answered
1
Under what situations is the iterative DFA algorithm correct?
2
How precise is the solution produced by it?
3
Will the algorithm converge?
4
What is the meaning of a “solution”?
The above questions can be answered accurately by a
DFA framework
Further, reusable components of the DFA algorithm can be
identi?ed once a framework is de?ned
A DFA framework (D;V;^;F) consists of
D : A direction of the data?ow, either forward or backward
V : A domain of values
^ : A meet operator (V;^) form a semi-lattice
F : A family of transfer functions, V! V
F includes constant transfer functions for the
ENTRY/EXIT nodes as well
Y .N. Srikant Theoretical Foundations of DFA
Page 3


Data-?ow Analysis: Theoretical Foundations -
Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Theoretical Foundations of DFA
Foundations of Data-?ow Analysis
Basic questions to be answered
1
Under what situations is the iterative DFA algorithm correct?
2
How precise is the solution produced by it?
3
Will the algorithm converge?
4
What is the meaning of a “solution”?
The above questions can be answered accurately by a
DFA framework
Further, reusable components of the DFA algorithm can be
identi?ed once a framework is de?ned
A DFA framework (D;V;^;F) consists of
D : A direction of the data?ow, either forward or backward
V : A domain of values
^ : A meet operator (V;^) form a semi-lattice
F : A family of transfer functions, V! V
F includes constant transfer functions for the
ENTRY/EXIT nodes as well
Y .N. Srikant Theoretical Foundations of DFA
Semi-Lattice
A semi-lattice is a set V and a binary operator^, such that
the following properties hold
1
V is closed under^
2
^ is idempotent (x^x = x), commutative (x^y = y^x),
and associative (x^(y^z) = (x^y)^z)
3
It has a top element,>, such that8 x2 V;>^x = x
4
It may have a bottom element,?, such that
8x2 V;?^x =?
The operator^ de?nes a partial order on V, such that
x y iff x^y = x
Any two elements x and y in a semi-lattice have a greatest
lower bound (glb), g, such that g = x^y; g x; g y,
and if z x; and z y, then z g
Y .N. Srikant Theoretical Foundations of DFA
Page 4


Data-?ow Analysis: Theoretical Foundations -
Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Theoretical Foundations of DFA
Foundations of Data-?ow Analysis
Basic questions to be answered
1
Under what situations is the iterative DFA algorithm correct?
2
How precise is the solution produced by it?
3
Will the algorithm converge?
4
What is the meaning of a “solution”?
The above questions can be answered accurately by a
DFA framework
Further, reusable components of the DFA algorithm can be
identi?ed once a framework is de?ned
A DFA framework (D;V;^;F) consists of
D : A direction of the data?ow, either forward or backward
V : A domain of values
^ : A meet operator (V;^) form a semi-lattice
F : A family of transfer functions, V! V
F includes constant transfer functions for the
ENTRY/EXIT nodes as well
Y .N. Srikant Theoretical Foundations of DFA
Semi-Lattice
A semi-lattice is a set V and a binary operator^, such that
the following properties hold
1
V is closed under^
2
^ is idempotent (x^x = x), commutative (x^y = y^x),
and associative (x^(y^z) = (x^y)^z)
3
It has a top element,>, such that8 x2 V;>^x = x
4
It may have a bottom element,?, such that
8x2 V;?^x =?
The operator^ de?nes a partial order on V, such that
x y iff x^y = x
Any two elements x and y in a semi-lattice have a greatest
lower bound (glb), g, such that g = x^y; g x; g y,
and if z x; and z y, then z g
Y .N. Srikant Theoretical Foundations of DFA
Semi-Lattice of Reaching De?nitions
3 de?nitions, {d1,d2,d3}
V is the set of all subsets of {d1,d2,d3}
^ is[
The diagram (next slide) shows the partial order relation
induced by^ (i.e.,[)
Partial order relation is
An arrow, y! x indicates x y (x y)
Each set in the diagram is a data-?ow value
Transitivity is implied in the diagram (a! b & b! c
imples a! c)
An ascending chain: (x
1
< x
2
<:::< x
n
)
Height of a semi-lattice: largest number of ‘<’ relations in
any ascending chain
Semi-lattices in our DF frameworks will be of ?nite height
Y .N. Srikant Theoretical Foundations of DFA
Page 5


Data-?ow Analysis: Theoretical Foundations -
Part 1
Y .N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Theoretical Foundations of DFA
Foundations of Data-?ow Analysis
Basic questions to be answered
1
Under what situations is the iterative DFA algorithm correct?
2
How precise is the solution produced by it?
3
Will the algorithm converge?
4
What is the meaning of a “solution”?
The above questions can be answered accurately by a
DFA framework
Further, reusable components of the DFA algorithm can be
identi?ed once a framework is de?ned
A DFA framework (D;V;^;F) consists of
D : A direction of the data?ow, either forward or backward
V : A domain of values
^ : A meet operator (V;^) form a semi-lattice
F : A family of transfer functions, V! V
F includes constant transfer functions for the
ENTRY/EXIT nodes as well
Y .N. Srikant Theoretical Foundations of DFA
Semi-Lattice
A semi-lattice is a set V and a binary operator^, such that
the following properties hold
1
V is closed under^
2
^ is idempotent (x^x = x), commutative (x^y = y^x),
and associative (x^(y^z) = (x^y)^z)
3
It has a top element,>, such that8 x2 V;>^x = x
4
It may have a bottom element,?, such that
8x2 V;?^x =?
The operator^ de?nes a partial order on V, such that
x y iff x^y = x
Any two elements x and y in a semi-lattice have a greatest
lower bound (glb), g, such that g = x^y; g x; g y,
and if z x; and z y, then z g
Y .N. Srikant Theoretical Foundations of DFA
Semi-Lattice of Reaching De?nitions
3 de?nitions, {d1,d2,d3}
V is the set of all subsets of {d1,d2,d3}
^ is[
The diagram (next slide) shows the partial order relation
induced by^ (i.e.,[)
Partial order relation is
An arrow, y! x indicates x y (x y)
Each set in the diagram is a data-?ow value
Transitivity is implied in the diagram (a! b & b! c
imples a! c)
An ascending chain: (x
1
< x
2
<:::< x
n
)
Height of a semi-lattice: largest number of ‘<’ relations in
any ascending chain
Semi-lattices in our DF frameworks will be of ?nite height
Y .N. Srikant Theoretical Foundations of DFA
Lattice Diagram of Reaching De?nitions
y! x indicates x y (x y)
Y .N. Srikant Theoretical Foundations of DFA
Read More