Abstract The program dependence graph (PDG) is being used in research projects for compilation to parallel architectures, program version integration and program semantics. This paper describes the methods used in a prototype Fortran‐to‐PDG translator called the PDG Testbed. Implementation decisions and details of the PDG Testbed project are described as a complement to the formal papers detailing the abstract PDG. In addition, experimental results are given that show the storage consumption for a PDG relative to a conventional internal representation as well as execution times for several analysis and optimization steps.

The Program Dependence Web (PDW) is a program representation that can be directly interpreted using control-, data-, or demand-driven models of execution. A PDW combines a single-assignment version of the program with explicit operators that manage the flow of data values. The PDW can be viewed as an augmented Program Dependence Graph. Translation to the PDW representation provides the basis for projects to compile Fortran onto dynamic dataflow architectures and simulators. A second application of the PDW is the construction of various compositional semantics for program dependence graphs.

Reduction in strength is a traditional transformation for speeding up loop execution on sequential processors. The inverse transformation, induction variable substitution, can also speed up loops by decreasing register requirements, although it is typically a normalizing step in the detection of array dependences by parallelizing compilers. The author presents a simple framework for performing these transformations. In contrast to previous approaches to strength reduction, no unnecessary temporary variables or dead code fragments are introduced, only relevant intermediate language fragments are examined, iteration test replacement is not handled as a special case, and the execution time of the target code is never increased. The method is particularly easy to visualize, making it a useful teaching tool as well.>

In this paper we present an intermediate program representation, called the program dependence graph ( PDG ), that makes explicit both the data and control dependences for each operation in a program. Data dependences have been used to represent only the relevant data flow relationships of a program. Control dependences are introduced to analogously represent only the essential control flow relationships of a program. Control dependences are derived from the usual control flow graph. Many traditional optimizations operate more efficiently on the PDG. Since dependences in the PDG connect computationally related parts of the program, a single walk of these dependences is sufficient to perform many optimizations. The PDG allows transformations such as vectorization, that previously required special treatment of control dependence, to be performed in a manner that is uniform for both control and data dependences. Program transformations that require interaction of the two dependence types can also be easily handled with our representation. As an example, an incremental approach to modifying data dependences resulting from branch deletion or loop unrolling is introduced. The PDG supports incremental optimization, permitting transformations to be triggered by one another and applied only to affected dependences.

A new program representation is presented which permits certain optimizations to be performed at less expense than with other forms. This paper describes code motion, common subexpression elimination and induction variable detection. Scalar propagation and constant folding are sketched here, but detailed elsewhere. The powerful code motion strategy allows entire regions of the program to be moved. The representation described may be used as a compiler intermediate form or simply as a model for program analysis. It has great potential for use in translation for parallel machines.