Jeanne Ferrante
Karl J. Ottenstein
Abstract
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.
- 1 AHO, A. V., SETHI, R., AND ULLMAN, J. D. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986. {An alternative reference is this book's predecessor, AHO, A. V. AND ULLMAN, J.D. Principles of Compiler Design. Addison-Wesley, 1977.} Google Scholar
- 2 ALBERGA, C. N., BROWN, A. L., LEEMAN, G. B., JR., MIKELSONS, M., AND WEGMAN, M. N. A program development tool. IBM J. Res. Dev 28, 1 (Jan. 1984). Google Scholar
- 3 ALLEN, F.E. Control flow analysis. In Proceedings of a Symposium on Compiler Optimization. SIGPLAN Not. 5, 7 (July 1970), 1-19. Google Scholar
- 4 ALLEN, F.E. Interprocedural analysis and the information derived by it. In Lecture Notes in Computer Science Vol. 23, Springer-Verlag, New York, 1974, 291-321. Google Scholar
- 5 ALLEN, F. E., AND COCKE, J. A catalogue of optimizing transformations. In Design and Optimization of Compilers, Randall Rustin, Ed., Prentice-Hall, Englewood Cliffs, NJ, 1972, 1-30.Google Scholar
- 6 ALLEN, F. E., COCKE, J., AND KENNEDY, K. Reduction of operator strength. In Program Flow Analysis, Theory and Applications, S. Muchnick and N. Jones, Eds., Prentice-Hall, Englewood Cliffs, NJ, 1981, 79-101.Google Scholar
- 7 ALLEN, J. R. Dependence analysis for subscripted variables and its application to program transformations. Ph.D. dissertation, Dept. of Computer Science, Rice University, Houston, TX, April 1983. Google Scholar
- 8 ALLEN, J. R., KENNEDY, K., PORTERFIELD, C., AND WARREN, J. Conversion of control dependence to data dependence. In Conference Record of the lOth Annual ACM Symposium on Principles o{ Programming Languages (Austin, Texas, Jan. 24-26, 1983), ACM, New York, 177-189. Google Scholar
- 9 ALLEN, J. R., AND KENNEDY, K. PFC: a program to convert FORTRAN to parallel form. Tech. Rep. 82-6, Dept. of Mathematical Sciences, Rice University, March 1982, 63 pages.Google Scholar
- 10 ALLEN, R., AND KENNEDY, K. Programming environments for supereomputers. In Supercomputers: Algorithms, Architectures, and Scientific Computation, F. A. Matsen and T. Tajima, Eds., University of Texas Press, Austin, TX, 1986, 19-38. Google Scholar
- 11 BANERJEE, U. Data dependence in ordinary programs. Report 76-837, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Nov. 1976.Google Scholar
- 12 BURKE, M. An interval analysis approach toward interprocedural data flow analysis. IBM Research Report RC 10640, T. J. Watson Research Center, Yorktown Heights, NY, July 1984.Google Scholar
- 13 BURKE, M., AND CYTRON, R. Interprocedural dependence analysis and parallelization. In Proceedings of the ACM SIGPLAN '86 Symposium on Compiler Construction (Paid Alto, CA, June 25-27, 1986). ACM SIGPLAN Not. 21, 7 (July 1986), 162-175. Google Scholar
- 14 COOPER, K., AND KENNEDY, K. Efficient computation of flow insensitive summary information. In Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction (Montreal, June 17-22, 1984). ACM SIGPLAN Not. 19, 6 (June 1984), 247-258. Google Scholar
- 15 COOPER, K. Analyzing aliases of reference formal parameters. In Conference Record o/the 12th ACM Symposium on Principles of Programming Languages (New Orleans, LA, Jan. 14-16, 1985), ACM, New York, 281-290. Google Scholar
- 16 CYTRON, R., LOWRY, A., AND ZADECK, K. Code motion of control structures in high-level languages. In Conference Record 13th Annual ACM Symposium on Principles of Programming Languages (St. Petersburg, FL, Jan. 13-15, 1986), ACM, New York, 70-85. Google Scholar
- 17 DAVID, A. L., AND KELLER, R.M. Data flow program graphs. IEEE Comput. 15, 2 (Feb. 1982), 26-41.Google Scholar
- 18 DENNIS, J.B. First version of a data flow procedure language, revised Comp. Struc. Group Memo 93 (MAC Tech. Memo 61) MIT LCS (May 1975) 21 pages.Google Scholar
- 19 DENNIS, J.B. Data flow supercomputers. IEEE Comput. 13, 11 (Nov. 1980), 48-56.Google Scholar
- 20 ELLCEY, S.J. The program dependence graph: interprocedural information representation and general space requirements. Master's thesis, Dept. of Computer Science, Michigan Technological Univ., Houghton, MI, Aug. 1985.Google Scholar
- 21 FERRANTE, J. The program dependence graph as a basis for node splitting transformations. IBM Research Rep. RC 10542, Yorktown Heights, NY, June 1984.Google Scholar
- 22 FERRANTE, J., AND MACE, M. On linearizing parallel code. In Conference Record of the 12th Annual ACM Symposium on Principles of Programming Languages (New Orleans, LA, Jan. 14-16, 1985), ACM, New York, 179-190. Google Scholar
- 23 FERRANTE, J., AND Oq~ENSTEIN, K. A program form based on data dependency in predicate regions. In Conference Record o/the lOth Annual ACM Symposium on Principles of Programming Languages (Austin, TX, Jan. 24-26, 1983), ACM, New York, 217-231. Google Scholar
- 24 FERRANTE, J., OTTENSTEIN, K., AND WARREN, g. D. The program dependence graph and its use in optimization. Lecture Notes in Computer Science Vol. 167, Springer-Verlag, 1984, 125-132. Google Scholar
- 25 GRAHAM, S., AND WEGMAN, M. A fast and usually linear algorithm for global flow analysis. J. ACM 23, 1 (Jan. 1976), 172-202. Google Scholar
- 26 HECHT, M.S. Flow Analysis of Computer Programs. Elsevier-North Holland, New York, 1977. Google Scholar
- 27 KAS'JANOV, V.N. Distinguishing hammocks in a directed graph. Soviet Math. Doklady 16, 5 (1975), 448--450.Google Scholar
- 28 KENNEDY, K. Automatic translation of FORTRAN programs to vector form. Report 476- 029-4, Dept. of Mathematical Sciences, Rice Univ., Houston, TX, June 1980.Google Scholar
- 29 KUCK, D.J. The Structure of Computers and Computations. Wiley, New York, 1978. Google Scholar
- 30 KUCK, D. J., KUHN, R. H., LEASURE, B., AND WOLFE, M. The structure of an advanced vectorizer for pipelined processors. In Proceedings IEEE 4th International COMPSAC (Chicago, IL, Oct. 1980), IEEE, New York, 709-715.Google Scholar
- 31 KUCK, D. J., KUHN, R. H., PADUA, D. A., LEASURE, B., AND WOLFE, M. Dependence graphs and compiler optlmizations. In 8th Annual ACM Symposium on Principles of Programming Languages (Williamsburg, VA, Jan. 26-28, 1981), ACM, New York, 207-218. Google Scholar
- 32 KUHN, R.H. Optimization and interconnection complexity for parallel processors, single-stage networks and decision trees. Ph.D. dissertation, Rep. 80-1009, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Feb. 1980. Google Scholar
- 33 LENGAUER, T., AND TARJAN, R.E. A fast algorithm for finding dominators in a fiowgraph. ACM Trans. Program. Lang. Syst. 1, 1 (July 1979), 121-141. Google Scholar
- 34 MCGRAW, J., SKEDZIELEWSKI, S., ALLAN, S., GRIT, D., OLDEHOEFT, R., GLAUERT, J., DOBES, I., AND HOHENSEE, P. SISAL: streams and iteration in a single-assignment language. Language reference manual version 1.1. Report M-146, Lawrence Livermore National Laboratory, July 20, 1983.Google Scholar
- 35 MIKELSONS, M. Prettyprinting in an interactive environment. In Proceedings of the ACM SIGPLAN/SIGOA Symposium on Text Manipulation (Portland, OR, June 1981), ACM, New York, 108-116. Google Scholar
- 36 OTTENSTEIN, K.J. Data-flow graphs as an intermediate program form. Ph.D. dissertation, Computer Sciences Dept., Purdue University, Lafayette, IN, Aug. 1978. Google Scholar
- 37 OTTENSTEIN, K.J. An intermediate program form based on a cyclic data-dependence graph. CS-TR 81-1, Dept. of Computer Science, Michigan Technological Univ., Houghton, MI, Oct. 1981; July 1982, errata.Google Scholar
- 38 OTTENSTEIN, K. J., AND OTTENSTEIN, L. M. The program dependence graph in a software development environment. In Proceedings of the ACM SIGPLAN/SIGSOFT Symposium on Practical Programming Development Environments (Pittsburgh, PA, April 23-25, 1984), ACM SIGPLAN Not. 19, 5 (May 1984), 177-184, and Softw. Eng. Notes 9, 3. Google Scholar
- 39 OTTENSTEIN, K.J. A simplified view of reduction in strength. CS-TR 85-4c, Michigan Technological Univ., Houghton, MI, Aug. 1986.Google Scholar
- 40 PADUA, D.A. Multiprocessors: discussion of some theoretical and practical problems. Ph.D. dissertation, Computer Sciences Dept., Univ. of Illinois, Urbana-Champaign, Sept. 1979. Google Scholar
- 41 PADUA, D. A., KUCK, D. J., AND LAWRIE, D. High-speed multiprocessors and their compilers. IEEE Trans. Comput. 29, 9 (Sept. 1980), 763-776.Google Scholar
- 42 REIF, J. H., AND LEWgS, H.R. Symbolic evaluation and the global value graph. In Conference Record of the 4th Annual ACM Symposium on Principles of Programming Languages (Los Angeles, CA, Jan. 17-19, 1977), ACM, New York, 104-118. Google Scholar
- 43 RYDER, B.G. Incremental data flow analysis. In Conference Record lOth Annual ACM Symposium on Principles of Programming Languages (Austin, TX, Jan. 1983), ACM, New York, 167-176. Google Scholar
- 44 SARKAR, V., AND HENNESSY, J. Compile-time partitioning and scheduling of parallel programs. In Proceedings of the ACM SIGPLAN Compiler Construction Conference (Palo Alto, CA, June 25-27, 1986), ACM SIGPLAN Not. 21, 7 (July 1986). Google Scholar
- 45 SARKAR, V., AND HENNESSY, J. Partitioning parallel programs for macro-datafiow. In Proceedings of the ACM Conference on LISP and Functional Programming (Cambridge, UK, Aug. 4-6, 1986), ACM, New York, 202-211. Google Scholar
- 46 SKEDZIELEWSKI, S., AND GLAUERT, J. IFI: an intermediate form for applicative langauges, draft 4. Lawrence Livermore National Laboratory, Livermore, CA, June 26, 1983.Google Scholar
- 47 TISCHLER, R., SCHAUFLER, R., AND PAYNE, C. Static analysis of programs as an aid to debugging. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on High-Level Debugging (Pacific Grove, CA, March 20-23, 1983), ACM Softw. Eng. Notes 8, 4 (Aug. 1983) and in ACM SIGPLAN Not. 18, 8 (Aug. 1983), 155-158. Google Scholar
- 48 TOWLE, R.A. Control and data dependence for program transformations. Ph.D. dissertation, Univ. of Illinois, Urbana-Champaign, Feb. 1976. Google Scholar
- 49 TRELEAVEN, P. C., HOPKINS, R. P., AND RAUTENBACH, P.W. Combining data flow and control flow computing. Comput. J. 25, 2 (1982), 208-217.Google Scholar
- 50 WARREN, J. A hierarchical basis for reordering transformations. In Conference Record of the 11th Annual ACM Symposium on Principles of Programming Languages (Salt Lake City, UT, Jan. 1984), ACM, New York, 272-282. Google Scholar
- 51 WATERS, R.C. The programmer's apprentice: knowledge based program editing. IEEE Trans. Softw. Eng. SE-8, I (Jan. 1982), 1-12.Google Scholar
- 52 WATERS, R.C. Automatic analysis of the logical structure of programs. AI-Lab TR-492, MIT, Cambridge, MA., Dec. 1978. Available as NTIS AD-A0$4 818. Google Scholar
- 53 WEGMAN, M. Summarizing graphs by regular expressions. In Conference Record of the lOth Annual ACM Symposium on Principles of Programming Languages (Austin, TX, Jan. 24-26, 1983), ACM, New York, 203-212. Google Scholar
- 54 WEISER, M. Program slicing. In Proceedings of the 5th International Conference on Software Engineering (San Diego, CA, March 9-12, 1981), IEEE Computer Society Press, New York, 439-449. Google Scholar
- 55 WEgSER, M. Programmers use slices when debugging. Commun. ACM 25, 7 (July 1982), 446-452. Google Scholar
- 56 WOLFE, M.J. Optimizing supercompilers for supercomputers. Ph.D. dissertation. Tech. Rep. UIUCDCS-R-82-1105, Univ. of Illinois, Urbana-Champaign, Oct. 1982. Google Scholar
Index Terms
- The program dependence graph and its use in optimization
Recommendations
On the control dependence in the program dependence graph
CSC '88: Proceedings of the 1988 ACM sixteenth annual conference on Computer scienceThe program dependence graph, PDG, is used to represent the data and control dependencies between the statements of some program. The data dependencies between the statements are fully understood and they correspond to the definition-use chain. On the ...
Fast condensation of the program dependence graph
PLDI '13Aggressive compiler optimizations are formulated around the Program Dependence Graph (PDG). Many techniques, including loop fission and parallelization are concerned primarily with dependence cycles in the PDG. The Directed Acyclic Graph of Strongly ...
Fast condensation of the program dependence graph
PLDI '13: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and ImplementationAggressive compiler optimizations are formulated around the Program Dependence Graph (PDG). Many techniques, including loop fission and parallelization are concerned primarily with dependence cycles in the PDG. The Directed Acyclic Graph of Strongly ...
Reviews
John R. Levine
The program dependence graph (PDG) is a program representation that combines control flow and data flow information into a single structure. The authors cite previous work on control dependence graphs, which represent control flow without data flow, and on data dependence graphs, which show data flow without control flow. The PDG combines data flow and control flow information into a single structure that is useful for a variety of program transformations and optimizations. Nodes in the PDG represent statements, expressions, and predicates, and edges represent data values passed from one expression to another and control conditions that influence the order of execution. The authors start by showing how to construct a PDG from the control and data flow information in the original program. They then describe some variants of the PDG that may be more convenient for different source languages or various applications. The next section shows some applications of the PDG. The authors show how it can be used to find parts of a program that can be made parallel, to do code motion and loop fusion optimizations, and to find the parts of a program that can affect a given variable, which is useful in debugging. Finally, they discuss incremental optimization, which involves updating the PDG as an optimization is made, rather than having to examine the whole program again. For example, if an optimization removes some dead code, the data dependencies for that dead code can be removed directly. They claim that this procedure is much faster than the conventional equivalent. The PDG certainly appears to be a powerful mechanism that unifies a broad class of program analyses and transformations. My primary concern is that it also appears to be too complicated to construct and very large; the authors' estimate is 50 percent larger than the equivalent triples although it seems to me that their estimate is conservative. Nonetheless, they sketch out some impressive results, and we will probably be seeing many more PDG applications in the near future.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments