J. R. Allen
ABSTRACT
Program analysis methods, especially those which support automatic vectorization, are based on the concept of interstatement dependence where a dependence holds between two statements when one of the statements computes values needed by the other. Powerful program transformation systems that convert sequential programs to a form more suitable for vector or parallel machines have been developed using this concept [AllK 82, KKLW 80].The dependence analysis in these systems is based on data dependence. In the presence of complex control flow, data dependence is not sufficient to transform programs because of the introduction of control dependences. A control dependence exists between two statements when the execution of one statement can prevent the execution of the other. Control dependences do not fit conveniently into dependence-based program translators.One solution is to convert all control dependences to data dependences by eliminating goto statements and introducing logical variables to control the execution of statements in the program. In this scheme, action statements are converted to IF statements. The variables in the conditional expression of an IF statement can be viewed as inputs to the statement being controlled. The result is that control dependences between statements become explicit data dependences expressed through the definitions and uses of the controlling logical variables.This paper presents a method for systematically converting control dependences to data dependences in this fashion. The algorithms presented here have been implemented in PFC, an experimental vectorizer written at Rice University.
- {AllK 82} J. R. Allen and K., Kennedy, "PFC: a program to convert Fortran to parallel form," Report MASC TR 82-6, Department of Mathematical Sciences, Rice University, Houston, Texas, March, 1982.Google Scholar
- {AlKW 82} J. R. Allen, K. Kennedy, and J., Warren, "Simplification of Boolean formulas in PFC," Dept. Mathematical Sciences, Rice University, Houston, Texas, NovemberGoogle Scholar
- {ANSI 81} American National Standards Institute. Inc., "Proposals approved for Fortran 8x," X3J3/S6.80 (preliminary document), November 30, 1981.Google Scholar
- {Bane 76} U. Banerjee, "Data dependence in ordinary programs," Report 76-837, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, November 1976.Google Scholar
- {BohJ 66} C. Bohm and G. Jacopini, "Flow diagrams, Turing machines, and languages with only two formation rules," Comm ACM 9, 5, May 1966. Google ScholarDigital Library
- {Burr 77} Burroughs Corporations, "Implementation of FORTRAN," Burroughs Scientific Processor brochure, 1977.Google Scholar
- {GibK 81} C. Gibbons, and K. Kennedy, "Simplification of functions," Rice Technical Report 476-029-10, Rice University, January 1981.Google Scholar
- {Hare 80} D. Harel, "On folk theorems," Comm ACM 23, 5, July 1980, 379-389. Google ScholarDigital Library
- {Kenn 80} K. Kennedy, "Automatic translation of Fortran programs to vector form," Rice Technical Report 476-029-4, Rice University, October 1980.Google Scholar
- {Kuck 77} D. J. Kuck, "A survey of parallel machine organization and programming," Computing Surveys 9, 1, March 1977, 29-59. Google ScholarDigital Library
- {KKLP 81} D. J. Kuck, R. H. Kuhn, B. Leasure, D. A. Padua, and M. Wolfe, "Compiler transformation of dependence graphs," Conf. Record of the Eighth ACM Symposium on Principles of Programming Languages, Williamsburg, Va., January 1981.Google Scholar
- {KKLW 80} D. J. Kuck, R. H. Kuhn, B. Leasure, and M. Wolfe, "The structure of an advanced vectorizer for pipelined processors," Proc. IEEE Computer Society Fourth International Computer Software and Applications Conf. IEEE, Chicago, October 1980.Google Scholar
- {McCl 56} E. J. McCluskey, "Minimization of Boolean functions," Bell System Tech. J. 35, 5, November 1956, 1417-1444.Google ScholarCross Ref
- {Quin 52} W. V. Quine, "The problem of simplifying truth functions," Am. Math. Monthly 59, 8, October 1952, 521-531.Google ScholarCross Ref
- {Towl 76} R. A. Towle, "Control and data dependence for program transformations," Ph.D. Dissertation, Report 76-788, Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, March 1976. Google ScholarDigital Library
- {Wolf 78} M. J. Wolfe, "Techniques for improving the inherent parallelism in program," Report 78-929, Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois. July 1978.Google Scholar
Recommendations
Computation of interprocedural control dependence
ISSTA '98: Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysisProgram dependence information is useful for a variety of software testing and maintenance tasks. Properly defined, control and data dependencies can be used to identify semantic dependencies. To function effectively on whole programs, tools that ...
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 ...
Tail dependence functions and vine copulas
Tail dependence and conditional tail dependence functions describe, respectively, the tail probabilities and conditional tail probabilities of a copula at various relative scales. The properties as well as the interplay of these two functions are ...
Comments