Download Paper - STS

2.3 Dataflow Analysis to Find Equivalent Warnings
Inn =


∅


n is the entry block
T
Outn
otherwise
p∈predecessors(n)
Outn = (Genn + Inn ) − Killn (Genn + Inn )
(
{e}
n has a warning with e as its EOI
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.4: Forwards Dataflow Equations to Find Equivalent Warnings [6]
is not empty, we know that the expression contains the modified variable and we need
to kill it. Concluding, the formal definition coincides with the informal explanation.
Next we can apply the equations to our CFG to see how these work. Starting with
the first block, we get that the In1 is the empty set since it is the entry block. In the
first block, we have a warning. Therefore, the gen set contains the expression 1/x. Now
we have to check the kill set. The variable h is modified in the first block. Though, no
expression of Gen1 + In1 , which evaluates to {1/x}, contains h. Thus, the intersection
of h and x is empty and we do not kill anything. At the exit of the first block we have,
Out1 = {1/x}
Assuming that In3 is the empty set, we get that Out3 is {1/x} with the same argumentation as in the first block. In4 is the intersection of all its predecessors. The
fourth block has the third block as the only predecessor, leaving us with Out3 = In4 .
The fourth block has no warning, so the gen set is empty. However, we modify the
variable x. The set modifiedVars contains the left side of the statement, namely x. Intersecting the set containing x with the variables of {1/x} results in the non-empty set
{x}. Therefore, {1/x} is in the kill set. The set at the exit of block four is therefore
Out4 = {1/x} − {1/x} = ∅.
Now we can calculate In2 . It is the intersection of Out1 and Out4 . Intersecting {1/x}
with ∅ leaves us with ∅. The second block has no warning and we do not modify any
variable. Therefore, we have In2 = Out2 = ∅. Knowing that Out2 is the empty set, we
also know that our assumption for In3 holds and that we do not have to enter it again.
The fifth and sixth block are still not calculated. Out2 defines In5 that is the empty
11