Conversion of control dependence to data dependence

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.

REFERENCES

• 1: {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.
• 2: {AlKW 82} J. R. Allen, K. Kennedy, and J., Warren, "Simplification of Boolean formulas in PFC," Dept. Mathematical Sciences, Rice University, Houston, Texas, November
• 3: {ANSI 81} American National Standards Institute. Inc., "Proposals approved for Fortran 8x," X3J3/S6.80 (preliminary document), November 30, 1981.
• 4: {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.
• 5: Corrado Böhm , Giuseppe Jacopini, Flow diagrams, turing machines and languages with only two formation rules, Communications of the ACM, v.9 n.5, p.366-371, May 1966 [doi>10.1145/355592.365646]
• 6: {Burr 77} Burroughs Corporations, "Implementation of FORTRAN," Burroughs Scientific Processor brochure, 1977.
• 7: {GibK 81} C. Gibbons, and K. Kennedy, "Simplification of functions," Rice Technical Report 476-029-10, Rice University, January 1981.
• 8: David Harel, On folk theorems, Communications of the ACM, v.23 n.7, p.379-389, July 1980 [doi>10.1145/358886.358892]
• 9: {Kenn 80} K. Kennedy, "Automatic translation of Fortran programs to vector form," Rice Technical Report 476-029-4, Rice University, October 1980.
• 10: David J. Kuck, A Survey of Parallel Machine Organization and Programming, ACM Computing Surveys (CSUR), v.9 n.1, p.29-59, March 1977 [doi>10.1145/356683.356686]
• 11: {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.
• 12: {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.
• 13: {McCl 56} E. J. McCluskey, "Minimization of Boolean functions," Bell System Tech. J. 35, 5, November 1956, 1417-1444.
• 14: {Quin 52} W. V. Quine, "The problem of simplifying truth functions," Am. Math. Monthly 59, 8, October 1952, 521-531.
• 15: Ross Albert Towle, Control and data dependence for program transformations., 1976
• 16: {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.