Data-flow 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-flow 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
identified once a framework is defined
A DFA framework (D, V , ∧, F ) consists of
D : A direction of the dataflow, 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 that ∀ x ∈ V , > ∧ x = x
4 It may have a bottom element, ⊥, such that
∀x ∈ V , ⊥ ∧ x = ⊥
The operator ∧ defines 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
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-flow 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
identified once a framework is defined
A DFA framework (D, V , ∧, F ) consists of
D : A direction of the dataflow, 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 that ∀ x ∈ V , > ∧ x = x
4 It may have a bottom element, ⊥, such that
∀x ∈ V , ⊥ ∧ x = ⊥
The operator ∧ defines 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
