Browse Prior Art Database

Improved Convergence of Global Data Flow Equations

IP.com Disclosure Number: IPCOM000101972D
Original Publication Date: 1990-Oct-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 6 page(s) / 233K

Publishing Venue

IBM

Related People

Hicks, DR: AUTHOR [+2]

Abstract

This article describes ways to improve the efficiency of obtaining the solution for forward and backward data flow equations through two techniques: 1. Quicker detection of convergence when it has occurred 2. (For backward data flow equations only) dynamically adjusting the order of solution

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 29% of the total text.

Improved Convergence of Global Data Flow Equations

       This article describes ways to improve the efficiency of
obtaining the solution for forward and backward data flow equations
through two techniques:
   1.  Quicker detection of convergence when it has occurred
   2.  (For backward data flow equations only) dynamically adjusting
the order of solution

      Fig. 1 is a flow graph illustrating the first technique for
forward data flow problems.  The equations being solved are
represented in Fig. 2.

      These are the equations used to compute the forward data flow
attributes in steps 4 and 7.  The second equation is referred to as
the "transfer" equation.  In and out represent the attributes at
entry and exit to a block, B. Gen indicates whether the attribute is
generated by a block B, and transp indicates whether the attribute is
transparent in a block B.

      -  First Technique
  The first technique (the quicker detection of convergence) stems
from the fact that if depth-first order is used to solve a forward
data flow problem (or if reverse of depth-first order is used to
solve a backward data flow problem), then the only changes which can
create a need to make a subsequent pass over the system of equations
are those changes which propagate over "retreating edges" (retreating
edges are those edges in the data flow graph which correspond to
backward branches in a program).  This is shown in steps 5 and 6.
Step 5 tests to see if the data flow attributes computed in step 4
have changed.  If they have, step 6 tests to see if they need to be
propagated "backward" on "retreating edges".

      Additionally, even though a change may propagate along a
retreating edge, it frequently does not cause a change in the output
of the equation to which it propagates.  This can occur when the
effects of the propagated change are masked either due to other
inputs to the propagated-to equation (i.e., other out[P] values in
the first equation above) or to its transfer function.  In practice,
masking due to other inputs is quite common, since in well-structured
programs, the block corresponding to the propagated-to equation
"dominates" the loop.

      Thus, when a change is propagated over a retreating edge,
rather than setting the variable "Loop" immediately, step 7
recomputes the forward data flow attributes for the propagated-to
block, and only if its output changes is the variable "Loop" set to
"TRUE". This indicates that another loop through the data flow
equations is necessary to factor in the effect of the changed
attributes previously processed blocks.

      Although this occasionally results in additional effort (in
those cases where "Loop" is already marked "TRUE"), it can
potentially save an entire pass over the system of equations.  The
additional effort can be further reduced to a negligible amount by
observing that the whole purpose of steps 6 through 9 is to set
"Loop" to "TRUE" if a signif...