Optimization of range checking

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimization of range checking

Full text

Pdf (385 KB)

Source

Symposium on Compiler Construction archive
Proceedings of the 1982 SIGPLAN symposium on Compiler construction table of contents

Boston, Massachusetts, United States

Pages: 114 - 119

Year of Publication: 1982

ISBN:0-89791-074-5

Also published in ...

Authors

Victoria Markstein	IBM Thomas J. Watson Research Center, P. O. Box 218, Yorktown Heights, New York
John Cocke
Peter Markstein

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 35, Citation Count: 27

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/800230.806986 What is a DOI?

ABSTRACT

An analysis is given for optimizing run-time range checks in regions of high execution frequency. These optimizations are accomplished using strength reduction, code motion and common subexpression elimination. Test programs, using the above optimizations, are used to illustrate run-time improvements.

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	F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
	2	Cocke J. and Markstein P., Measurement of Code Improvement Algorithms, Proceedings of IFIPS (1980); 221-228.
	3	Harrison W., Compiler Analysis of the Value Ranges for Variables, IEEE Transactions on Software Engineering, (May 1977); 243-250.
	4	Schwartz J.T., On Programming - An Interim Report on the SETL Project. Installment II: The SETL Language and Examples of Its Use, Courant Institute of Mathematical Sciences, N.Y.U., (1973); 293-310.
	5	Welsh, J., Economic Range Checks in Pascal, Software - Practice and Experience, (1978); Vol. 8, 85-97

CITED BY 27

	François Bourdoncle, Abstract debugging of higher-order imperative languages, ACM SIGPLAN Notices, v.28 n.6, p.46-55, June 1993
	Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, ACM SIGPLAN Notices, v.17 n.6, p.22-31, June 1982
	Priyadarshan Kolte , Michael Wolfe, Elimination of redundant array subscript range checks, ACM SIGPLAN Notices, v.30 n.6, p.270-278, June 1995
	Jonathan M. Asuru, Optimization of array subscript range checks, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.109-118, June 1992
	Aneesh Aggarwal , Keith H. Randall, Related field analysis, ACM SIGPLAN Notices, v.36 n.5, p.214-220, May 2001
	Rajiv Gupta, A fresh look at optimizing array bound checking, ACM SIGPLAN Notices, v.25 n.6, p.272-282, Jun. 1990
	Rajiv Gupta, Optimizing array bound checks using flow analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.135-150, March–Dec. 1993
	Wei-Ngan Chin , Eak-Khoon Goh, A reexamination of “Optimization of array subscript range checks”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.217-227, March 1995
	Rastislav Bodík , Rajiv Gupta , Vivek Sarkar, ABCD: eliminating array bounds checks on demand, ACM SIGPLAN Notices, v.35 n.5, p.321-333, May 2000
	Rajiv Gupta , Madalene Spezialetti, Loop monotonic computations: an approach for the efficient run-time detection of races, Proceedings of the symposium on Testing, analysis, and verification, p.98-111, October 08-10, 1991, Victoria, British Columbia, Canada
	Mikel Luján , Mikel Luján , John R. Gurd , T. L. Freeman , José Miguel, Elimination of Java array bounds checks in the presence of indirection, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.76-85, November 03-05, 2002, Seattle, Washington, USA
	Radu Rugina , Martin Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, ACM SIGPLAN Notices, v.35 n.5, p.182-195, May 2000
	Suan Hsi Yong , Susan Horwitz, Protecting C programs from attacks via invalid pointer dereferences, ACM SIGSOFT Software Engineering Notes, v.28 n.5, September 2003
	Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, ACM SIGPLAN Notices, v.39 n.4, April 2004
	José E. Moreira , Samuel P. Midkiff , Manish Gupta, From flop to megaflops: Java for technical computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.265-295, March 2000
	Hongwei Xi , Frank Pfenning, Eliminating array bound checking through dependent types, ACM SIGPLAN Notices, v.33 n.5, p.249-257, May 1998
	Sheri J. Bernstein , Robert S. Duff, Optimizing Ada on the fly, ACM SIGAda Ada Letters, v.XIX n.3, p.169-179, Sept. 1999
	S. P. Midkiff , J. E. Moreira , M. Snir, Optimizing array reference checking in Java programs, IBM Systems Journal, v.37 n.3, p.409-453, 1998
	Madalene Spezialetti , Rajiv Gupta, Loop Monotonic Statements, IEEE Transactions on Software Engineering, v.21 n.6, p.497-505, June 1995
	Radu Rugina , Martin C. Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.2, p.185-235, March 2005
	J. A. N. Lee, Biographies, IEEE Annals of the History of Computing, v.24 n.4, p.53-55, October 2002
	Thi Viet Nga Nguyen , François Irigoin, Efficient and effective array bound checking, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.527-570, May 2005
	Nikolai Joukov , Aditya Kashyap , Gopalan Sivathanu , Erez Zadok, An electric fence for kernel buffers, Proceedings of the 2005 ACM workshop on Storage security and survivability, November 11-11, 2005, Fairfax, VA, USA
	Suan Hsi Yong , Susan Horwitz, Using Static Analysis to Reduce Dynamic Analysis Overhead, Formal Methods in System Design, v.27 n.3, p.313-334, November 2005
	V. Vijay Kumar , K. V. N. Sunitha, Optimization on array bound check and redundancy elimination, Proceedings of the 5th WSEAS/IASME International Conference on Systems Theory and Scientific Computation, p.266-271, September 15-17, 2005, Malta
	Chris Bentley , Scott A. Watterson , David K. Lowenthal , Barry Rountree, Implicit array bounds checking on 64-bit architectures, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.4, p.502-527, December 2006
	Lixin Su , Mikko H. Lipasti, Speculative optimization using hardware-monitored guarded regions for java virtual machines, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA