Article

Free access

Elimination of redundant array subscript range checks

Authors:

Priyadarshan Kolte,

Michael WolfeAuthors Info & Claims

PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation

Pages 270 - 278

https://doi.org/10.1145/207110.207160

Published: 01 June 1995 Publication History

Abstract

This paper presents a compiler optimization algorithm to reduce the run time overhead of array subscript range checks in programs without compromising safety. The algorithm is based on partial redundancy elimination and it incorporates previously developed algorithms for range check optimization. We implemented the algorithm in our research compiler, Nascent, and conducted experiments on a suite of 10 benchmark programs to obtain four results: (1) the execution overhead of naive range checking is high enough to merit optimization, (2) there are substantial differences between various optimizations, (3) loop-based optimizations that hoist checks out of loops are effective in eliminating about 98% of the range checks, and (4) more sophisticated analysis and optimization algorithms produce very marginal benefits.

References

[1]

A. V. Aho, R. Sethi, and J. D. Ullman. Compilers, Principles, Techniques, and Tools. Addison-Wesley, 1986.

Digital Library

[2]

J. M. Asuru. Optimization of array subscript range checks. A CM Letters on Programming Languages and Systems, vol. 1, no. 2, 109-118, June 1992.

Digital Library

[3]

P. Briggs and K. D. Cooper. Effective partial redundancy elimination. Proceedings of the A CM SIGPLAN '94 Conference on Programming Language Design and Implementation, i59-170, June, 1994.

Digital Library

[4]

P. Cousot and R. Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. Conference Record of the jtn A CM Symposzum on Principles of Programming Languages, 238-252, January, 1977.

Digital Library

[5]

P. Cousot and N. Halbwachs. Automatic discovery of linear restraints among variables of a program. Conference Record of the 5~n A CM Symposium on Principles of Programming Languages, 84-96, January, 1978.

Digital Library

[6]

R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. A CM Transactions on Programming Languages and Systems, vol. 13, no. 4, pp. 451-490, October, 1991.

Digital Library

[7]

M. P. GerIek, E. Stoltz, and M. Wolfe. Beyond induction variables: Detecting and classifying sequences using a demand-driven SSA form. A CM Transactions on Programming Languages and Systems, to appear.

Digital Library

[8]

S. M. German. Automating proofs of the absence of common runtime errors. Conference Record of the 5tn A CM Symposium on Principles of Programming Languages, 105-118, January, 1978.

Digital Library

[9]

R. Gupta. A flesh look at optimizing array bound checking. Proceedings of the A CM SIGPLAN '90 Conference on Programm~ng Language Design and Implementation, 272-282, June, 1990.

Digital Library

[10]

R. Gupta. Optimizing array bound checks using flow analysis. A CM Letters on Programming Languages and Systems, vol. 2, nos. 1-4, 135-150, March-December, 1993.

Digital Library

[11]

W. H. Harrison. Compiler analysis for the value ranges for variables. IEEE Transactzons on Software Engineemng, SE- 3, 3, 243-250, May, 1977.

[12]

J. Knoop, O. Rfithing, and B. Steffen. Lazy code motion. Proceedings of the A CM SIGPLAN '92 Conference on Programmzng Language Design and Implementation, 224-234, June, 1992.

Digital Library

[13]

V. Markstein, J. Cocke, and P. Markstein. Optimization of range checking. Proceedings of the SIGPLAN '82 Symposium on Compiler Constructwn, 114-119, June 1982.

Digital Library

[14]

E. Morel. Data flow analysis and global optimization, in Method6 and tools for compiler construction, B. Lorho (ed.), Cambridge University Press, New York, 289-315, 1984.

Digital Library

[15]

E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies. Communications of the A CM, vol. 2, no. 2, 96-103, February, 1979.

Digital Library

[16]

B. Schwarz, W. Kirchgassner, and R. Landwehr. An optimizer for Ada - design, experiences and results. Proceedings SIGPLA1V '88 Conference on Programr~zng Language Design and Implementation, 175-185, June, 1988.

Digital Library

[17]

N. Suzuki and K. Ishihata. Implementation of an array bound checker. Conference Record of the 4tn A CM Symposium on Principles of Programming Languages, 132-143, J anu ary, 1977.

Digital Library

[18]

M. Wolfe. Beyond induction variables. Proceedings o{ the A CM SIGPLAN '92 Conference on Programming Language Design and implementation, 162-174, June, 1992.

Digital Library

Cited By

Blache G(2019)Handling index-out-of-bounds in safety-critical embedded C code using model-based developmentSoftware and Systems Modeling (SoSyM)10.1007/s10270-018-0697-y18:3(1795-1807)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10270-018-0697-y
Blache GBaudry BCombemale BKienzle JPretschner A(2016)Handling index-out-of-bounds in safety-critical embedded C code using model-based developmentProceedings of the ACM/IEEE 19th International Conference on Model Driven Engineering Languages and Systems10.1145/2976767.2976803(143-149)Online publication date: 2-Oct-2016
https://dl.acm.org/doi/10.1145/2976767.2976803
Absar JShekhar DProbst CWimmer C(2011)Eliminating partially-redundant array-bounds check in the Android Dalvik JIT compilerProceedings of the 9th International Conference on Principles and Practice of Programming in Java10.1145/2093157.2093175(121-128)Online publication date: 24-Aug-2011
https://dl.acm.org/doi/10.1145/2093157.2093175
Show More Cited By

Index Terms

Elimination of redundant array subscript range checks
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
      2. Language types
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs

Recommendations

Elimination of redundant array subscript range checks

This paper presents a compiler optimization algorithm to reduce the run time overhead of array subscript range checks in programs without compromising safety. The algorithm is based on partial redundancy elimination and it incorporates previously ...
Optimization of array subscript range checks

Compile-time elimination of subscript range checks is performed by some optimizing compilers to reduce the overhead associated with manipulating array data structures. Elimination and propagation, the two methods of subscript range check optimization, ...
A reexamination of “Optimization of array subscript range checks”

Jonathan Asuru proposed recently an enhanced method for optimizing array subscript range checks. The proposed method is however unsafe and may generate optimized programs whose behavior is different from the original program. Two main flaws in Asuru's ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation

June 1995

335 pages

ISBN:0897916972

DOI:10.1145/207110

Chairman:
David W. Wall
Digital—Western Research Laboratory

ACM SIGPLAN Notices Volume 30, Issue 6
June 1995
327 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/223428
Editors:
Brent T. Hailpern
IBM T. J. Watson Research Center, Yorktown Heoghts, NY
,
Richard L. Wexelblat
IRS IS:AO, Washington, DC
Issue’s Table of Contents

Copyright © 1995 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI95

Sponsor:

SIGPLAN

PLDI95: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 18 - 21, 1995

California, La Jolla, USA

Acceptance Rates

PLDI '95 Paper Acceptance Rate 28 of 105 submissions, 27%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
620
Total Downloads

Downloads (Last 12 months)103
Downloads (Last 6 weeks)20

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Blache G(2019)Handling index-out-of-bounds in safety-critical embedded C code using model-based developmentSoftware and Systems Modeling (SoSyM)10.1007/s10270-018-0697-y18:3(1795-1807)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10270-018-0697-y
Blache GBaudry BCombemale BKienzle JPretschner A(2016)Handling index-out-of-bounds in safety-critical embedded C code using model-based developmentProceedings of the ACM/IEEE 19th International Conference on Model Driven Engineering Languages and Systems10.1145/2976767.2976803(143-149)Online publication date: 2-Oct-2016
https://dl.acm.org/doi/10.1145/2976767.2976803
Absar JShekhar DProbst CWimmer C(2011)Eliminating partially-redundant array-bounds check in the Android Dalvik JIT compilerProceedings of the 9th International Conference on Principles and Practice of Programming in Java10.1145/2093157.2093175(121-128)Online publication date: 24-Aug-2011
https://dl.acm.org/doi/10.1145/2093157.2093175
Erhardt CStilkerich MLohmann DSchröder-Preikschat WWellings ARavn A(2011)Exploiting static application knowledge in a Java compiler for embedded systemsProceedings of the 9th International Workshop on Java Technologies for Real-Time and Embedded Systems10.1145/2043910.2043927(96-105)Online publication date: 26-Sep-2011
https://dl.acm.org/doi/10.1145/2043910.2043927
Tzannes ACaragea GBarua RVishkin U(2010)Lazy binary-splittingACM SIGPLAN Notices10.1145/1837853.169347945:5(179-190)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1837853.1693479
Hoefler TSiebert CLumsdaine A(2010)Scalable communication protocols for dynamic sparse data exchangeACM SIGPLAN Notices10.1145/1837853.169347645:5(159-168)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1837853.1693476
Choi JSingh AVuduc R(2010)Model-driven autotuning of sparse matrix-vector multiply on GPUsACM SIGPLAN Notices10.1145/1837853.169347145:5(115-126)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1837853.1693471
Baghsorkhi SDelahaye MPatel SGropp WHwu W(2010)An adaptive performance modeling tool for GPU architecturesACM SIGPLAN Notices10.1145/1837853.169347045:5(105-114)Online publication date: 9-Jan-2010
https://dl.acm.org/doi/10.1145/1837853.1693470
Lei Zhou Kefei Chen (2010)Recursive symbolic bound analysis in loop structure2010 The 2nd International Conference on Computer and Automation Engineering (ICCAE)10.1109/ICCAE.2010.5451995(76-80)Online publication date: Feb-2010
https://doi.org/10.1109/ICCAE.2010.5451995
Chiueh T(2008)Fast bounds checking using debug registerProceedings of the 3rd international conference on High performance embedded architectures and compilers10.5555/1786054.1786066(99-113)Online publication date: 27-Jan-2008
https://dl.acm.org/doi/10.5555/1786054.1786066
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents