Efficient Computation of Expressions with Common Subexpressions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient Computation of Expressions with Common Subexpressions

Full text

Pdf (1.11 MB)

Source

Journal of the ACM (JACM) archive
Volume 27 , Issue 1 (January 1980) table of contents

Pages: 146 - 163

Year of Publication: 1980

ISSN:0004-5411

Authors

Bhaskaram Prabhala	Computer Science Department, Indiana University, Bloomington, IN and The Pennsylvania State University, University Park, Pennsylvania
Ravi Sethi	Department of Computer Science, The University of Arizona, Tucson, AZ and Bell Laboratories, Murray Hill, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 25, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322169.322182 What is a DOI?

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	ABDELoWAHAB, H. M, AND KAMEDA, T Scheduling to minimize maximum cumulative cost subject to seriesparallel precedence constraints Oper. Res. 26, I (Jan-Feb. 1978), 141-158.
	2	ABDEL-WAHAB, H M, AND KAMEDA, T. On the C-optimal scheduling problem Unpubhshed manusctpt, Umverstty of Waterloo, Waterloo, Ontario, Canada, 1978
	3	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	4	A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
	5	A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
	6	A. V. Aho , S. C. Johnson , J. D. Ullman, Code-generation for machines with multiregister operations, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512953]
	7	Alfred V. Aho , Ravi Sethi, How Hard is Compiler Code Generation?, Proceedings of the Fourth Colloquium on Automata, Languages and Programming, p.1-15, July 18-22, 1977
	8	Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
	9	BEATY, J C Register assignment algorithm for generation of highly optimized object code IBM J. Res Develop I8, 1 (Jan 1974), 20-39
	10	J. L. Bruno , T. Lassagne, The Generation of Optimal Code for Stack Machines, Journal of the ACM (JACM), v.22 n.3, p.382-396, July 1975 [doi>10.1145/321892.321901]
	11	John Bruno , Ravi Sethi, Code Generation for a One-Register Machine, Journal of the ACM (JACM), v.23 n.3, p.502-510, July 1976 [doi>10.1145/321958.321971]
	12	A. P. Ershov, On programming of arithmetic operations, Communications of the ACM, v.1 n.8, p.3-6, Aug. 1958 [doi>10.1145/368892.368907]
	13	HARRISON, W A class of register allocation algorithms Res Rep RC-5342, IBM Thomas J Watson Res Center, Yorktown Heights, N.Y, 1975
	14	S. C. Johnson, A portable compiler: theory and practice, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-104, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512771]
	15	KIM, J , AND TAN, C J Register assignment algonthm lI Res. Rep RC-6262, IBM Thomas J Watson Res Center, Yorktown Heights, N Y, 1976
	16	LAWLER, EL Sequencmgjobs to mlmmize total weighted completlon time subject to precedence constralnts Ann Discrete Math 2 (1978), 75-90
	17	Ikuo Nakata, On compiling algorithms for arithmetic expressions, Communications of the ACM, v.10 n.8, p.492-494, Aug. 1967 [doi>10.1145/363534.363549]
	18	Bhaskaram Prabhala , Ravi Sethi, A comparison of instruction sets for stack machines, Proceedings of the ninth annual ACM symposium on Theory of computing, p.132-142, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803403]
	19	R. R. Redziejowski, On arithmetic expressions and trees, Communications of the ACM, v.12 n.2, p.81-84, Feb. 1969 [doi>10.1145/362848.362859]
	20	RIORDAN, J, AND SHANNON, C E The number of two terminal series parallel networks J Math Phys 21 (1942), 83-93
	21	Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
	22	TARJAN, R E. Depth first search and linear graph algorithms SlAM .L Comptng 1, 2 (June 1972), 146-160
	23	Jacobo Valdes , Robert E. Tarjan , Eugene L. Lawler, The recognition of Series Parallel digraphs, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.1-12, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804393]
	24	William M. Waite, Optimization, Compiler Construction, An Advanced Course, 2nd ed., p.549-602, January 1976
	25	William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975
	26	YHAP, E F General register assignment in the presence of data flow Res Rep RC-5645, IBM Thomas J Watson Res Center, Yorktown Heights, N Y, 1975

CITED BY 3

	Guido Araujo , Sharad Malik, Code generation for fixed-point DSPs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.2, p.136-161, April 1998
	Peter Marwedel, A new synthesis for the MIMOLA software system, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.271-277, July 1986, Las Vegas, Nevada, United States
	Henry G. Baker, Linear logic and permutation stacks—the Forth shall be first, ACM SIGARCH Computer Architecture News, v.22 n.1, p.34-43, March 1994