InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Efficient Data Flow Analysis Package

IP.com Disclosure Number: IPCOM000052833D
Original Publication Date: 1981-Jul-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 4 page(s) / 34K

Publishing Venue


Related People

Rutledge, JD: AUTHOR


Procedures are described for solving data flow problems and include the idea of generating code which is then executed to solve the data flow problems.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 36% of the total text.

Page 1 of 4

Efficient Data Flow Analysis Package

Procedures are described for solving data flow problems and include the idea of generating code which is then executed to solve the data flow problems.

In an optimizing compiler, it is required to solve repeatedly a variety of problems which may be classed as data flow analysis problems. These include the usual reach, exposure, common expression, and constant propagation as well as many others, not all well known at the beginning of the design process. These have in common that they are equivalent to the solution of systems of linear equations over some mathematical structure depending on the particular problem, often but not necessarily a semi-ring, where the structure of the equation system, i.e., the number of equations and the pattern of non-zero coefficients, depends only on the control flow of the program. On the other hand, mathematical structure, including the operations of ""multiplication'' and ""addition'', depends on the particular problem, and the values of the coefficients depend on the detailed operations of the program. If the proper level of control flow representation is chosen, the structure of the equation system is stable under most optimizing transformations, while the operations associated with each segment of control flow change as code is moved, redundancies are eliminated, etc. Hence, repeated solutions are required with differing coefficients but with the same structure.

It has been observed that the control flow graphs of most "natural' programs are reducible, and that most of the remainder fail to be so only in a small subgraph, when seen from the proper viewpoint. Therefore, any method for the solution of linear systems over such graphs should take advantage of this structure. Algorithms have been proposed, e.g., in [2], which are very nearly linear in the number of edges N in the graph, i.e., the number of operations is bounded by a nearly-constant function of N multiplied by N.

A program package is described to deal with this problem in a near-optimal way and includes the following: 1. Factoring of dependencies, embodied in: a. Test interface which contains all dependencies on the format of input text. b. Graph Builder and Reduction Sequence Generator. This derives the control graph and generates straight/line code for the solution of arbitrary data/flow problems over the graph and its reverses. The code is an over/head/free sequence of calls on subroutines which perform the actual operations, which are problem dependent. Control flow optimization is performed here incidentally, since text can be scanned through the graph, omitting unnecessary labels, branches, etc. This technique of performing the housekeeping overhead once to generate a sequence of substantive operation instructions to be executed many times has a long history, most notably in sparse matrix techniques of numerical analysis, but this is its first use in this context, and also the first in which...