Dependence graphs and compiler optimizations

ABSTRACT

Dependence graphs can be used as a vehicle for formulating and implementing compiler optimizations. This paper defines such graphs and discusses two kinds of transformations. The first are simple rewriting transformations that remove dependence arcs. The second are abstraction transformations that deal more globally with a dependence graph. These transformations have been implemented and applied to several different types of high-speed architectures.

REFERENCES

• 1: {AbKL79} W. Abu-Sufah, D. Kuck, and D. Lawrie, "Automatic Program Transformations for Virtual Memory Computers," Proc. of the 1979 Nat'l. Computer Conf., pp. 969-974, June 1979.
• 2: W. B. Acherman , J. B. Dennis , William B Ackerman, VAL- ORIENTED ALGORITHMIC LANGUAGE, PRELIMINARY REFERENCE MANUAL, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 3: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 4: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 5: {AlCo72} F. E. Allen and J. Cocke, "A Catalogue of Optimizing Transformations," in Design and Optimization of Compilers (R. Rustin, Ed.), Prentice-Hall, Inc., NJ, pp. 1-30, 1972.
• 6: {ArGP78} Arvind, K. P. Gostelow, and W. Plouffe, "An Asynchronous Programming Language and Computing Machine," University of California at Irvine, CA, Dept. of Information and Computer Science Rpt. 114a, Dec. 1978.
• 7: {AsMa75} E. Ascroft and Z. Manna, "Translating Program Schemes to While-Schemas," SIAM J. on Computing, Vol. 4, No. 2, pp. 125-146, June 1975.
• 8: {BaGK80} U. Banerjee, D. Gajski, and D. J. Kuck, "Array Machine Control Units for Loops Containing IFs," Proc. of the 1980 Int'l. Conf. on Parallel Processing, Harbor Springs, MI, pp. 28-36, Aug. 1980.
• 9: Brenda S. Baker, An Algorithm for Structuring Flowgraphs, Journal of the ACM (JACM), v.24 n.1, p.98-120, Jan. 1977 [doi>10.1145/321992.321999]
• 10: {Bane76} U. Banerjee, "Data Dependence in Ordinary Programs," M. S. thesis, Univ. of Ill. at Urbana-Champaign, Dept. of Comput. Sci. Rpt. No. 76-837, Nov. 1976.
• 11: Utpal Banerjee, Speedup of ordinary programs, 1979
• 12: {BCKT79} U. Banerjee, S. C. Chen, D. J. Kuck, and R. A. Towle, "Time and Parallel Processor Bounds for Fortran-Like Loops," IEEE Trans. on Computers, Vol. C-28, No. 9, pp. 660-670, Sept. 1979.
• 13: {Beat74} J. C. Beatty, "Register Assignment Algorithm for Generation of Highly Optimized Object Code," IBM J. of Res. and Dev., Vol. 18, No. 1, pp. 20-39, Jan. 1974.
• 14: 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]
• 15: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 16: {DayW70} W. H. E. Day, "Compiler Assignment of Data Items to Registers," IBM Systs. J., Vol. 9, No. 4, pp. 281-317, 1970.
• 17: {DuKn78} D. D. Dunlop and J. C. Knight, "Register Allocation in the SL/1 Compiler," Proc. of the 1978 LASL Workshop on Vector & Parallel Processors, LA-7491-C, Los Alamos, NM, pp. 205-211, Sept. 1978.
• 18: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 19: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 20: {KKLW80} D. J. Kuck, R. H. Kuhn, B. Leasure, and M. Wolfe, "Analysis and Transformation of Programs for Parallel Computation," to appear in Proc. of the Fourth Int'l. Computer Software & Applications Conf., Oct. 1980.
• 21: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 22: {Kuck80} D. J. Kuck, Class Notes for C. S. 433, Univ. of Ill. at Urb.-Champ., Dept. of Comput. Sci., 1979.
• 23: {KuMC72} D. J. Kuck, Y. Muraoka, and S. C. Chen, "On the Number of Operations Simultaneously Executable in FORTRAN-Like Programs and Their Resulting Speed-Up," IEEE Trans. on Computers, Vol. C-21, No. 12, pp. 1293-1310, Dec. 1972.
• 24: David B. Loveman, Program Improvement by Source-to-Source Transformation, Journal of the ACM (JACM), v.24 n.1, p.121-145, Jan. 1977 [doi>10.1145/321992.322000]
• 25: {LuBa80} S. F. Lundstrom and G. H. Barnes, "A Controllable MIMD Architecture," Proc. of the 1980 Int'l. Conf. on Parallel Processing, pp. 19-27, Aug. 1980.
• 26: {PaKL80} D. A. Padua, D. J. Kuck, and D. H. Lawrie, "High-Speed Multiprocessors and Compilation Techniques," Special Issue on Parallel Processing, IEEE Trans. on Computers, Vol. C-29, No. 9, pp. 763-776, Sept. 1980.
• 27: {Park77} D. S. Parker, Jr., "Nonlinear Recurrences and Parallel Computation," in High Speed Computer and Algorithm Organization, pp. 317-320, Academic Press, Inc., 1977.
• 28: {ZeBa74} M. V. Zelkowitz and W. G. Bail, "Optimization of Structured Programs," Software Practice and Experience, Vol. 4, No. 1, pp. 51-57, 1974.