Optimal code motion

ABSTRACT

An implementation-oriented algorithm for lazy code motion is presented that minimizes the number of computations in programs while suppressing any unnecessary code motion in order to avoid superfluous register pressure. In particular, this variant of the original algorithm for lazy code motion works on flowgraphs whose nodes are basic blocks rather than single statements, since this format is standard in optimizing compilers. The theoretical foundations of the modified algorithm are given in the first part, where t-refined flowgraphs are introduced for simplifying the treatment of flow graphs whose nodes are basic blocks. The second part presents the “basic block” algorithm in standard notation and gives directions for its implementation in standard compiler environments.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. V. Aho , J. D. Ullman, Node listings for reducible flow graphs, Proceedings of seventh annual ACM symposium on Theory of computing, p.177-185, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803767]
	2	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	3	Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
	4	John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
	5	D. M. Dhamdhere, Practical adaption of the global optimization algorithm of Morel and Renvoise, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.291-294, April 1991 [doi>10.1145/103135.214520]
	6	DHAMDHERE, D. M. 1989. A new algorithm for composite hoisting and strength reduction optimlsation (+Corrigendum). Int. J. Comput Math. 27, 1, 1-14, 31-32.
	7	D. M. Dhamdhere, A fast algorithm for code movement optimisation, ACM SIGPLAN Notices, v.23 n.10, p.172-180, Oct. 1988 [doi>10.1145/51607.51621]
	8	DHAMDHERE, D.M. 1983. Characterization of program loops in code optimization J. Comput. Lang. 8, 2, 69-76.
	9	Dhananjay M. Dhamdhere , Uday P. Khedker, Complexity of bi-directional data flow analysis, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158696]
	10	D. M. Dhamdhere , Harish Patil, An elimination algorithm for bidirectional data flow problems using edge placement, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.312-336, April 1993 [doi>10.1145/169701.169684]
	11	Dhananjay M. Dhamdhere , Barry K. Rosen , F. Kenneth Zadeck, How to analyze large programs efficiently and informatively, ACM SIGPLAN Notices, v.27 n.7, p.212-223, July 1992
	12	Karl-Heinz Drechsler , Manfred P. Stadel, A variation of Knoop, Rüthing, and Steffen's Lazy Code Motion, ACM SIGPLAN Notices, v.28 n.5, p.29-38, May 1993 [doi>10.1145/152819.152823]
	13	Karl-Heinz Drechsler , Manfred P. Stadel, A solution to a problem with Morel and Renvoise's “Global optimization by suppression of partial redundancies”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.635-640, Oct. 1988 [doi>10.1145/48022.214509]
	14	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]
	15	Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
	16	HECHT, M. S. AND ULLMAN, J. D. 1977. A simple algorithm for global data flow analysis problems. SIAM J. Comput. 4, 4, 519-532.
	17	Matthew S. Hecht , Jeffrey D. Ullman, Analysis of a simple algorithm global data flow problems, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.207-217, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512946]
	18	Josm, S. M. AND DHAMDHERE, D.M. 1982a. A composite hoisting-strength reduction transformation for global program optimization--Part I. Int. J. Comput. Math. 11, 1, 21-41.
	19	JOSHI, S. M. AND DHAMDHERE, D.M. 1982b. A composite hoisting-strength reduction transformation for global program optimization--Part II. Int. J. Comput. Math. 11, 2, 111-126.
	20	John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
	21	K. W. Kennedy, Node listings applied to data flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.10-21, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512978]
	22	Jens Knoop , Bernhard Steffen, The Interprocedural Coincidence Theorem, Proceedings of the 4th International Conference on Compiler Construction, p.125-140, October 05-07, 1992
	23	KNOOP, J. AND STEFFEN, B. 1992b. Optimal interprocedural partial redundancy elimination. Extended abstract. In Addenda to Proceedings of the 4th Conference on Compiler Constructzon (CC). Lecture Notes in Computer Science. Springer-Verlag, Berlin. Also, Tech. Rep. 103, Dept. of Computer Science, Univ. of Paderborn, Germany, 36-39.
	24	KNOOP, J., RUTHING, O., AND STEFFEN, B. 1993. Lazy strength reduction. J. Program. Lang. 1, 1, 71-91.
	25	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.27 n.7, p.224-234, July 1992
	26	E Morel, Data flow analysis and global optimization, Methods and tools for compiler construction, Cambridge University Press, New York, NY, 1984
	27	MOREL, E. AND RENVOISE, C. 1981. Interprocedural elimination of partial redundancies. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice Hall, Englewood Cliffs, N.J., 160-188.
	28	E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
	29	B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
	30	Arthur Sorkin, Some comments on “A solution to a problem with Morel and Renvoise's 'Global optimization by suppression of partial redundancies'”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.666-668, Oct. 1989 [doi>10.1145/69558.214513]
	31	Bernhard Steffen, Data Flow Analysis as Model Checking, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.346-365, September 24-27, 1991
	32	Bernhard Steffen , Jens Knoop , Oliver Rüthing, Efficient code motion and an adaption to strength reduction, Proceedings of the international joint conference on theory and practice of software development on Advances in distributed computing (ADC) and colloquium on combining paradigms for software development (CCPSD): Vol. 2, p.394-415, April 1991, Brighton, United Kingdom
	33	B. Steffen , J. Knoop , O. Rüthing, The value flow graph: a program representation for optimal program transformations, Proceedings of the third European symposium on programming on ESOP '90, p.389-405, May 1990, Copenhagen, Denmark
	34	Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
	35	Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981 [doi>10.1145/322261.322272]
	36	Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
	37	ULLMAN, J. D. 1973.Fast algorithms for the elimination of common subexpressions. Acta Informatica 2, 3, 191-213.