Download Paper - STS

2 Dataflow Analysis
May
Must
Forwards
Backwards
Table 2.3: Possible DFA Classification
The other two classification criteria are forward and backward analyses. The difference
is in which direction we go through the CFG. To be more precise, we go either from the
unique entry to the exit of the program or the other way around, i.e., from the exit to
the entry. Combining these possible analyses we have four basic types of DFA. Tab. 2.3
depicts the four basic types of DFA.
2.2.3 Formal Definition
A DFA is in general defined by its dataflow equations [4]. The dataflow equations for a
forwards analysis look as follows. For each block n in the CFG:
outn = transf ern (inn )
inn = joinp∈predn (outn )
The transfer function defines what we do in a block. Hence, the transfer function
specifies what kind of information we generate and what information we kill.
Inn =


∅


n is the entry block
T
Outn
otherwise
p∈predecessors(n)
Outn = (Genn + Inn ) − Killn (Genn + Inn )
(
{e} if n computes
Genn =
∅
otherwise
(
killInf o(X, n) n modifies at least one variable
Killn (X) =
∅
no variable is modified by n
killInf o(X, n) = {e ∈ X | (usedV ars(e) ∩ modif iedV ars(n)) 6= ∅}
usedV ars(e) = r-values from expression e
modif iedV ars(n) = l-values from program statement n
Figure 2.2: Dataflow Equations of a Must Analysis
6