| |
Contents
Related topics
In data flow analysis, one wants to get informations about certain
program points. These program points are usually situated before and after
program statements. A program in the WHILE
language is represented as a control flow graph (CFG) where the nodes in this graph
are the program statements and edges represent possible control flows.
The MFP (minimum fixed point) algorithm calculates
the information reaching a node by combining the information from all its predecessors.
The information just after a node is calculated by applying the transfer function of the
node. Together all equations of these two types for all nodes form a recursive equation
system. The goal of the MFP algorithm is to find a solution of this system of equations.
This is done iteratively: starting from the first program statement, the algorithm visits
all program points once or several times. At each visit, the corresponding information
is recomputed according to the equation for this point. This is done until a fixed
point is reached, i.e. when all equations are satisfied so that no further visits
lead to a change of information.
The nodes in the CFG that need to be visited by the algorithm
are stored in a worklist. (For detailed information about the implementation
of the MFP algorithm see below).
This worklist is a set of nodes for which the incoming data flow information has
changed so that the outgoing information must be updated.
In every step of the MFP algorithm, a node from the worklist is
selected and its outgoing data flow information is recalculated. If this causes a
change in the incoming information of its successors, the successors are inserted
into the worklist. When selecting a node from the worklist, the nodes which may
influence other nodes in the worklist are taken first.
The algorithm continues by selecting nodes from the worklist and
ends whenever there are no nodes left in the worklist. The description of the single
steps of the MFP algorithm is given in an example.
In PAG/WWW, one can view the iterations of the MFP algorithm in the analysis
results. There the control flow graph of the analyzed program is shown. For
an example see Figure 1.
Figure 1: Visualization of the MFP algorithm
The node that is currently visited is colored red
( ).
Nodes that have still to be visited are colored blue
( ).
These are the nodes that stand behind the current node in the worklist.
The green nodes aren't currently in the worklist.
(Figure 1 shows an intermediate step of the analysis.
If you wish to see the steps before and after, look at the
example.)
Each node is labeled with the corresponding program statement.
The information that reaches the node stands aside the incoming edges
( ).
The information in the red box
( )
is the one which is currently recomputed;
the red box still shows the old value.
The information in the blue boxes
( )
is the output information of the remaining nodes in the worklist;
it will be recomputed later.
As mentioned above, the MFP algorithm in PAG is implemented
by a worklist algorithm. It is presented in Figure 2 (where the worklist is called
workset).
To every edge e, a value v(e) is assigned which
represents the current information along the edge (after the application of the
transfer function of the edge). Initially, v(e) is the specified initialisation
value init, often  .
Nodes that have to be inspected are contained in the worklist.
Initially, the worklist consists only of the start node s. In each step of the
algorithm, a node n is selected and removed from the worklist. First, the current
information x at this node is computed. For the start node s, it is the
specified start value start, and for all other nodes, it is obtained as
lub ( )
of the information at its incoming edges. For each outgoing edge e = (n,m),
the new information y = tf(e)(x) at this edge is computed. Then the algorithm
checks whether this value y is different from the old value v(e).
If so, the value of v(e) is updated and the end node m of e
is inserted into the worklist. (If y = v(e), nothing happens; in particular,
the end node is not inserted into the worklist.)
The computation continues until the worklist is empty. In this
situation, v(e) would not change anymore if the iteration were continued.
Then for each node n, MFP(n) can be obtained in the same manner as
the value x in the algorithm.
» Example run of the algorithm.
|
|
Figure 2: Worklist iteration
|
Search
| |
