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 DFARead More