Download Paper - STS
Transcript
2.2 Forward Data Flow Analysis
{}
h = 1/x 1
{}
{x 6= 0}
h = 1/x 1
{}
{x 6= 0}
{x}
h = 1/x 2
{x 6= 0}
h = 1/x 2
h = 1/x 1
{x 6= 0}
{x}
{x 6= 0}
h = 1/x 2
{x 6= 0}
{x}
x=y
3
h = 1/x 4
x=y
{x 6= 0}
Figure 2.3: Step 1
3
h = 1/x 4
x=y
{x 6= 0}
Figure 2.4: Step 2
3
h = 1/x 4
{x 6= 0}
Figure 2.5: Step 3
Now, we can apply our analysis to the program. At the start of the analysis, there is
no possibility that we already saw a warning. Therefore, the edge that enters the entry
block is annotated with the empty set of flow data. In Figure 2.3, the first step with the
initial information is displayed.
The second step is shown in Figure 2.4. In the second step, we encounter a block for
the first time. For that block, we have to calculate the flow data. We want to add a
variable to the flow data if it is the subject of a division-by-zero warning. Further, we
remove variables if they are reassigned. In the first block, we encounter the statement
h = 1/x. To the right of the block, we see that we have a division-by-zero warning
concerning the variable x. Hence, we insert the variable x to our flow data.
Now, we still have to remove the variables that got reassigned in the statement. The
variable h is reassigned in that statement. Thus, we have to remove it from our flow
data. However, the variable is not in our flow data and removing an element that is
not in the set does not chance anything. So, our calculation result is the new flow data
containing the variable x. We pass that flow data on to the next blocks, by attaching
it to the outgoing edges. Here, we only have one outgoing edge with only one successor
block.
We enter the second statement with the knowledge that x cannot be zero since the
variable is in the flow data. In the third step, we calculate the flow data using the
information we gain from the second statement in combination with the entering flow
data. In the second block, we again have the statement h = 1/x. To the right of
the statement we see that we have a division-by-zero warning concerning the variable
x. Thus, we add the variable to our flow data. The flow data already contains x so its
addition does not change the flow data. In the statement, we reassign h again. Therefore,
we have to remove it from our flow data leaving us with the set containing x. We pass
7