D. J. Kuck
R. H. Kuhn
D. A. Padua
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.
- {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.Google Scholar
- {AcDe79} W. B. Ackerman and J. B. Dennis, "Val--A Value-Oriented Algorithmic Language: Preliminary Reference Manual," Lab. for Computer Science (TR-218), MIT, Cambridge, MA, June 1979. Google ScholarDigital Library
- {AhHU74} A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, MA, 1974. Google ScholarDigital Library
- {AhU173} A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Vol. 2: Compiling, Prentice-Hall, Englewood Cliffs, NJ, 1973. Google ScholarDigital Library
- {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.Google Scholar
- {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.Google Scholar
- {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.Google ScholarCross Ref
- {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.Google Scholar
- {Bake77} B. S. Baker, "An Algorithm for Structuring Flow Graphs," J. of the ACM, Vol. 24, No. 1, pp. 98-120, Jan. 1977. Google ScholarDigital Library
- {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.Google Scholar
- {Bane79} U. Banerjee, "Speedup of Ordinary Programs," Ph.D. thesis, Univ. of Ill. at Urb.-Champ., Dept. of Comput. Sci. Rpt. No. 79-989, Oct. 1979. Google ScholarDigital Library
- {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.Google Scholar
- {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.Google ScholarDigital Library
- {BoJa66} C. Bohm and G. Jacopini, "Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules," Comm. of the ACM, Vol. 9, No. 5, pp. 366-371, May 1966. Google ScholarDigital Library
- {Cock70} J. Cocke, "Global Subexpression Elimination," SIGPLAN Notices, Vol. 5, No. 7, pp. 20-24, 1970. Google ScholarDigital Library
- {DayW70} W. H. E. Day, "Compiler Assignment of Data Items to Registers," IBM Systs. J., Vol. 9, No. 4, pp. 281-317, 1970.Google ScholarDigital Library
- {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.Google Scholar
- {Grie71} D. Gries, Compiler Construction for Digital Computers, Wiley & Sons, NY, 1971. Google ScholarDigital Library
- {GrWe76} S. L. Graham and M. Wegman, "A Fast and Usually Linear Algorithm for Global Flow Analysis," J. of the ACM, Vol. 23, No. 1, pp. 172-202, 1976. Google ScholarDigital Library
- {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.Google Scholar
- {Kuck78} D. J. Kuck, The Structure of Computers and Computations, Vol. I, John Wiley & Sons, Inc., NY, 1978. Google ScholarDigital Library
- {Kuck80} D. J. Kuck, Class Notes for C. S. 433, Univ. of Ill. at Urb.-Champ., Dept. of Comput. Sci., 1979.Google Scholar
- {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.Google Scholar
- {Love77} D. B. Loveman, "Program Improvement by Source-to-Source Transformation," J. of the ACM, Vol. 20, No. 1, pp. 121-145, Jan. 1977. Google ScholarDigital Library
- {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.Google Scholar
- {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.Google Scholar
- {Park77} D. S. Parker, Jr., "Nonlinear Recurrences and Parallel Computation," in High Speed Computer and Algorithm Organization, pp. 317-320, Academic Press, Inc., 1977.Google Scholar
- {ZeBa74} M. V. Zelkowitz and W. G. Bail, "Optimization of Structured Programs," Software Practice and Experience, Vol. 4, No. 1, pp. 51-57, 1974.Google ScholarCross Ref
- Dependence graphs and compiler optimizations
Recommendations
Collapsible graphs and Hamiltonian connectedness of line graphs
Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai [Z.-H. Chen, H.-J. Lai, Reduction techniques for super-Eulerian graphs and related topics-an update, in: Ku Tung-Hsin (Ed.), Combinatorics and Graph Theory, vol. 95, ...
Comparability Graphs Among Cover-Incomparability Graphs
Algorithms and Discrete Applied MathematicsAbstractComparability graphs and cover-incomparability graphs (C-I graphs) are two interesting classes of graphs from posets. Comparability graph of a poset is a graph with vertex set V and two vertices u and v are adjacent in V if u and v are ...
Equimatchable Graphs on Surfaces
A graph G is equimatchable if each matching in G is a subset of a maximum-size matching and it is factor critical if G-v has a perfect matching for each vertex v of G. It is known that any 2-connected equimatchable graph is either bipartite or factor ...
Comments