Abstract interpretation and low-level code optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Abstract interpretation and low-level code optimization

Full text

Pdf (1.23 MB)

Source

ACM/SIGPLAN Workshop Partial Evaluation and Semantics-Based Program Manipulation archive
Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation table of contents

La Jolla, California, United States

Pages: 111 - 121

Year of Publication: 1995

ISBN:0-89791-720-0

Author

Saumya Debray

Department of Computer Science, University of Arizona, Tucson, AZ

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 8, Citation Count: 0

Additional Information:

references 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/215465.215571 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	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	2	Alexander Aiken , Edward L. Wimmers , T. K. Lakshman, Soft typing with conditional types, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177847]
	3	Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
	4	A. W. Appel and Z. Shao, "An Empirical and Analytical Study of Stack vs. Heap Cost for Languages with Closures", Research Report CS-TR-450-94, Dept. of Computer Science, Princeton University, March 1994.
	5	J. Arsac , Y. Kodratoff, Some Techniques for Recursion Removal from Recursive Functions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.295-322, April 1982 [doi>10.1145/357162.357171]
	6	David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
	7	Peter A. Bigot , David Gudeman , Saumya Debray, Output value placement in moded logic programs, Proceedings of the eleventh international conference on Logic programming, p.175-189, August 1994
	8	P. A. Bigot and S. K. Debray, "A Simple Approach to Supporting Untagged Objects in Dynamically Typed Languages", Draft Report, Dept. of Computer Science, University of Arizona, Tucson, Nov. 1994.
	9	D. Bernstein , M. Golumbic , y. Mansour , R. Pinter , D. Goldin , H. Krawczyk , I. Nahshon, Spill code minimization techniques for optimizing compliers, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.258-263, June 19-23, 1989, Portland, Oregon, United States
	10	R. S. Bird, Tabulation Techniques for Recursive Programs, ACM Computing Surveys (CSUR), v.12 n.4, p.403-417, Dec. 1980 [doi>10.1145/356827.356831]
	11	Bror Bjerner , S. Holmström, A composition approach to time analysis of first order lazy functional programs, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.157-165, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99382]
	12	F. Bueno , M. García de la Banda , M. Hermenegildo, Effectiveness of global analysis in strict independence-based automatic parallelization, Proceedings of the 1994 International Symposium on Logic programming, p.320-336, November 1994, Symposia, Melbourne
	13	R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
	14	Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, ACM SIGPLAN Notices, v.29 n.11, p.252-262, Nov. 1994
	15	G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
	16	Craig David Chambers, The design and implementation of the self compiler, an optimizing compiler for object-oriented programming languages, Stanford University, Stanford, CA, 1992
	17	D. R. Chase, Safety consideration for storage allocation optimizations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.1-10, June 20-24, 1988, Atlanta, Georgia, United States
	18	David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
	19	Wei-Ngan Chin, Safe fusion of functional expressions, Proceedings of the 1992 ACM conference on LISP and functional programming, p.11-20, June 22-24, 1992, San Francisco, California, United States
	20	Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
	21	Jacques Cohen , Carl Zuckerman, Two languages for estimating program efficiency, Communications of the ACM, v.17 n.6, p.301-308, June 1974 [doi>10.1145/355616.361015]
	22	Keith D. Cooper , Mary W. Hall , Linda Torczon, Unexpected side effects of inline substitution: a case study, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.22-32, March 1992 [doi>10.1145/130616.130619]
	23	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	24	Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
	25	P. Cousot, "Semantic Foundations of Program Analysis", in Program Flow Analysis: Theory and Applications, eds. S. S. Muchnick and N. D. Jones, Prentice-Hall, 1981.
	26	Jack W. Davidson , Anne M. Holler, Subprogram Inlining: A Study of its Effects on Program Execution Time, IEEE Transactions on Software Engineering, v.18 n.2, p.89-102, February 1992 [doi>10.1109/32.121752]
	27	Koen De Bosschere , Saumya Debray , David Gudeman , Sampath Kannan, Call forwarding: a simple interprocedural optimization technique for dynamically typed languages, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.409-420, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178041]
	28	Jeffrey Dean , Craig Chambers, Towards better inlining decisions using inlining trials, Proceedings of the 1994 ACM conference on LISP and functional programming, p.273-282, June 27-29, 1994, Orlando, Florida, United States
	29	Saumya K. Debray, Optimizing almost-tail-recursive PROLOG programs, Proc. of a conference on Functional programming languages and computer architecture, p.204-219, January 1985, Nancy, France
	30	Saumya K. Debray , David S. Warren, Automatic mode inference for logic programs, Journal of Logic Programming, v.5 n.3, p.207-229, Sept. 1988 [doi>10.1016/0743-1066(88)90010-6]
	31	Saumya K. Debray , Nai-Wei Lin , Manuel Hermnegildo, Task granularity analysis in logic programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.174-188, June 1990, White Plains, New York, United States
	32	Saumya K. Debray , Nai-Wei Lin, Cost analysis of logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.826-875, Nov. 1993 [doi>10.1145/161468.161472]
	33	Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States [doi>10.1145/96709.96725]
	34	Dawson R. Engler , Todd A. Proebsting, DCG: an efficient, retargetable dynamic code generation system, ACM SIGPLAN Notices, v.29 n.11, p.263-272, Nov. 1994
	35	I. Foster and W. Winsborough, "Copy Avoidance through Compile-Time Analysis and Local Reuse", Proc. 1991 International Symposium on Logic Programming, San Diego, Nov. 1991, pp. 455-469. MIT Press, Cambridge.
	36	Philip B. Gibbons , Steven S. Muchnick, Efficient instruction scheduling for a pipelined architecture, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.11-16, June 25-27, 1986, Palo Alto, California, United States
	37	K. Gopinath , J. L. Hennessy, Copy elimination in functional languages, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.303-314, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75304]
	38	D. Gudeman, K. De Bosschere, and S.K. Debray, "j c: An Efficient and Portable Sequential Implementation of Janus", Proc. Joint Int. Conf. and Symp. on Logic Programming, Nov. 1992, pp. 399- 413. MIT Press.
	39	Fritz Henglein , Jesper Jørgensen, Formally optimal boxing, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.213-226, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177874]
	40	M. Hermenegildo and K. Greene, "The &- Prolog System: Exploiting Independent And- Parallelism", New Generation Computzng vol. 9 nos. 3-4, 1991, pp. 233-257.
	41	M. V. Hermenegildo , R. Warren , S. K. Debray, Global flow analysis as a practical compilation tool, Journal of Logic Programming, v.13 n.4, p.349-366, Aug. 1992 [doi>10.1016/0743-1066(92)90053-6]
	42	Paul Hudak , Adrienne Bloss, The aggregate update problem in functional programming systems, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.300-314, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318660]
	43	Lorenz Huelsbergen , James R. Larus , Alexander Aiken, Using the run-time sizes of data structures to guide parallel-thread creation, Proceedings of the 1994 ACM conference on LISP and functional programming, p.79-90, June 27-29, 1994, Orlando, Florida, United States
	44	S. Kaplan, "Algorithmic Complexity of Logic Programs", Proc. Fifth International Conference on Logic Programming, Seattle, 1988, pp. 780-793. MIT Press.
	45	D. Keppel, S. J. Eggers, and R. R. Henry, "A Case for Runtime Code Generation", Technical Report 91-11-04, Department of Computer Science, University of Washington, 1991.
	46	David Andrew Kranz , Paul Hudak, Orbit: an optimizing compiler for scheme, 1988
	47	David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
	48	Daniel Le Métayer, ACE: an automatic complexity evaluator, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.248-266, April 1988 [doi>10.1145/42190.42347]
	49	Xavier Leroy, Unboxed objects and polymorphic typing, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.177-188, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143205]
	50	Timothy S. McNerney, Verifying the correctness of compiler transformations on basic blocks using abstract interpretation, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.106-115, June 17-19, 1991, New Haven, Connecticut, United States
	51	A. Mari~in, G. Janssens, A. Mulkers, and M. Brhynooghe, "The Impact of Abstract Interpretation on Code Generation: an Experiment in Code Generation", Proc. Sixth International Conference on Logic Programming, Lisbon, Portugal, June 1989. MIT Press.
	52	Dieter Maurer, Strictness computation using special &lgr;-expressions, on Programs as data objects, p.136-155, April 1986, Copenhagen, Denmark
	53	Anne Mulkers , William Winsborough , Maurice Bruynooghe, Analysis of shared data structures for compile-time garbage collection in logic programs, Logic programming, MIT Press, Cambridge, MA, 1990
	54	Anne Mulkers , William Winsborough , Maurice Bruynooghe, Live-structure dataflow analysis for Prolog, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.2, p.205-258, March 1994 [doi>10.1145/174662.174664]
	55	Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
	56	John Peterson, Untagged data in tagged environments: choosing optimal representations at compile time, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.89-99, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99377]
	57	Simon L. Peyton Jones , John Launchbury, Unboxed values as first class citizens in a non-strict functional language, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.636-666, June 1991, Cambridge, Massachusetts, United States
	58	Michael L. Powell, A portable optimizing compiler for Modula-2, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.310-319, June 17-22, 1984, Montreal, Canada
	59	Todd A. Proebsting , Charles N. Fischer, Linear-time, optimal code scheduling for delayed-load architectures, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.256-267, June 24-28, 1991, Toronto, Ontario, Canada
	60	Lyle Harold Ramshaw, Formalizing the analysis of algorithms., 1979
	61	Brian Reistad , David K. Gifford, Static dependent costs for estimating execution time, Proceedings of the 1994 ACM conference on LISP and functional programming, p.65-78, June 27-29, 1994, Orlando, Florida, United States
	62	Stephen E. Richardson, Evaluating interprocedural code optimization techniques, Stanford University, Stanford, CA, 1992
	63	Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
	64	D. Sands, Complexity analysis for a lazy higher-order language, Proceedings of the third European symposium on programming on ESOP '90, p.361-376, May 1990, Copenhagen, Denmark
	65	Edmond Schonberg , Jacob T. Schwartz , Micha Sharir, An Automatic Technique for Selection of Data Representations in SETL Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.2, p.126-143, April 1981 [doi>10.1145/357133.357135]
	66	Micha Sharir, Some Observations Concerning Formal Differentiation of Set Theoretic Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.196-225, April 1982 [doi>10.1145/357162.357166]
	67	J. Shultis, "On the Complexity of Higher-Order Programs", Technical Report CU-CS-288, University of Colorado, Feb. 1985.
	68	Andrew Taylor, LIPS on MIPS: results from Prolog compiler for a RISC, Logic programming, MIT Press, Cambridge, MA, 1990
	69	A. Taylor, High Performance Prolog Implementation, Ph.D. thesis, University Of Sidney, Australia, 1991.
	70	K. Thompson, "A New C Compiler", Proc. Summer 1990 UKUUG Conference, London, July 1990, pp. 41-51.
	71	Peter Lodewijk Van Roy, Can logic programming execute as fast as imperative programming?, University of California at Berkeley, Berkeley, CA, 1991
	72	P. Wadler, Strictness analysis aids time analysis, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.119-132, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73571]
	73	Philip Wadler, Deforestation: transforming programs to eliminate trees, Proceedings of the Second European Symposium on Programming, p.231-248, January 1988, Nancy, France
	74	Tim A. Wagner , Vance Maverick , Susan L. Graham , Michael A. Harrison, Accurate static estimators for program optimization, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.85-96, June 20-24, 1994, Orlando, Florida, United States
	75	David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada
	76	Ben Wegbreit, Mechanical program analysis, Communications of the ACM, v.18 n.9, p.528-539, Sept. 1975 [doi>10.1145/361002.361016]
	77	Ben Wegbreit, Verifying Program Performance, Journal of the ACM (JACM), v.23 n.4, p.691-699, Oct. 1976 [doi>10.1145/321978.321987]
	78	Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada