article

Free access

ABCD: eliminating array bounds checks on demand

Authors:

Rastislav Bodík,

Vivek SarkarAuthors Info & Claims

ACM SIGPLAN Notices, Volume 35, Issue 5

Pages 321 - 333

https://doi.org/10.1145/358438.349342

Published: 01 May 2000 Publication History

Abstract

To guarantee typesafe execution, Java and other strongly typed languages require bounds checking of array accesses. Because array-bounds checks may raise exceptions, they block code motion of instructions with side effects, thus preventing many useful code optimizations, such as partial redundancy elimination or instruction scheduling of memory operations. Furthermore, because it is not expressible at bytecode level, the elimination of bounds checks can only be performed at run time, after the bytecode program is loaded. Using existing powerful bounds-check optimizers at run time is not feasible, however, because they are too heavyweight for the dynamic compilation setting.

ABCD is a light-weight algorithm for elimination of Array Bounds Checks on Demand. Its design emphasizes simplicity and efficiency. In essence, ABCD works by adding a few edges to the SSA value graph and performing a simple traversal of the graph. Despite its simplicity, ABCD is surprisingly powerful. On our benchmarks, ABCD removes on average 45% of dynamic bound check instructions, sometimes achieving near-ideal optimization.

The efficiency of ABCD stems from two factors. First, ABCD works on a sparse representation. As a result, it requires on average fewer than 10 simple analysis steps per bounds check. Second, ABCD is demand-driven. It can be applied to a set of frequently executed (hot) bounds checks, which makes it suitable for the dynamic-compilation setting, in which compile-time cost is constrained but hot statements are known.

References

[1]

J.M. Asuru. Optimization of array subscript range checks. ACM Letters on Programming Languages and Systems, 1(2):109-118, June 1992.]]

Digital Library

[2]

Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting equalities of variables in programs. In 15th Annual ACM Symposium on Principles of Programming Languages, pages 1-11, San Diego, California, January 1988.]]

Digital Library

[3]

M.G. Burke, J.-D. Choi, S. Fink, D. Grove, M. Hind, V. Sarkar, M.J. Serrano, V.C. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapefio Dynamic Optimizing Compiler for Java. In ACM Java Grande Conference, June 1999.]]

Digital Library

[4]

Claude Berge. Graphs and Hypergraphs (transl: E. Minieka). North-Holland, Amsterdam, 1973.]]

Digital Library

[5]

Rastislav Bodik, Rajiv Gupta, and Mary Lou Sofia. Interprocedural conditional branch elimination. In Proceedings of the ACM SIGPLAN '97 Conf. on Prog. Language Design and Impl., pages 146-158, June 1997.]]

Digital Library

[6]

Rastislav Bodik, Rajiv Gupta, and Mary Lou Sofia. Complete removal of redundant expressions. In Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, pages 1-14, June 1998.]]

Digital Library

[7]

Rastislav Bodik, Rajiv Gupta, and Mary Lou Sofia. Load-reuse analysis: Design and evaluation. In Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, May 1999.]]

Digital Library

[8]

F. Chow, S. Chan, R. Kennedy, S.-M. Liu, R. Lo, and P. Tu. A new algorithm for partial redundancy elimination based on SSA form. In Proceedings of the ACM SIGPLAN '97 Conf. on Prog. Language Design and Impl., pages 273-286, June 1997.]]

Digital Library

[9]

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991.]]

Digital Library

[10]

T H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to algorithms (Chapter 25.5, pages 539-543). MIT Press and McGraw-Hill Book Company, 1992.]]

Digital Library

[11]

Evelyn Duesterwald, Rajiv Gupta, and Mary Lou Sofia. A practical framework for demand-driven interprocedural data flow analysis. ACM Transactions on Programming Languages and Systems, 19(6):992-1030, November 1997.]]

Digital Library

[12]

G Gallo, G Longo, S Pallottino, and Sang Nguyen. Directed hypergraphs and applications. Discrete Applied Mathematics, 42:177-201, 1993.]]

Digital Library

[13]

Rajiv Gupta. A fresh look at optimizing array bound checking. In Mark Scott Johnson, editor, Proceedings of the ACM SIG- PLAN '90 Conference on Programming Language Design and Implementation (SIGPLAN '90), pages 272-282, White Plains, NY, USA, June 1990. ACM Press.]]

Digital Library

[14]

R. Gupta. Optimizing array bound checks using flow analysis. ACM Letters on Programming Languages and Systems, 1('- 4):135-150, March-December 1994.]]

Digital Library

[15]

Susan L. Graham and Mark Wegman. A fast and usually linear algorithm for global flow analysis. Communications of the ACM, 18(12):716-716, December 1975.]]

Digital Library

[16]

W.H. Harrison. Compiler analysis for the value ranges of variables. IEEE Transactions on Software Engineering, SE- 3(3):243-250, May 1977.]]

Digital Library

[17]

Rebecca Hasti and Susan Horwitz. Using static single assignment form to improve flow-insensitive pointer analysis. In Proceedings of the ACM SIGPLAN'98 Conference on Programming Language Design and lmplementation (PLDI), pages 97- 105, Montreal, Canada, 17-19 June 1998.]]

Digital Library

[18]

Susan Horwitz, Thomas Reps, and Mooly Sagiv. Demand Interprocedural Dataflow Analysis. In Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, pages 104-115, October 1995.]]

Digital Library

[19]

Richard Johnson and Keshav Pingali. Dependence-based program analysis. Proceedings of the ACM SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 78-89, June 1993.]]

Digital Library

[20]

Jens Knoop, Oliver Rtithing, and Bernhard Steffen. Lazy code motion. SIGPLAN Notices, 27(7):224-234, July 1992. Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation.]]

Digital Library

[21]

Kathleen Knobe and Vivek Sarkar. Array SSA form and its use in parallelization. In Conference Record of POPL '98: The 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 107-120, San Diego, California, 19-21 January 1998.]]

Digital Library

[22]

Priyadarshan Kolte and Michael Wolfe. Elimination of redundant array subscript range checks. ACM SIGPLAN Notices, 30(6):270-278, June 1995. Proceedings of the 1995 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI).]]

Digital Library

[23]

V. Markstein, J. Cocke, and P. Markstein. Optimization of range checking. In Proceedings of a Symposium on Compiler Optimization, pages 114-119, June 1982.]]

Digital Library

[24]

S.P. Midkiff, J. E. Moreira, and M. Snir. Optimizing bounds checking in Java programs. IBM Systems Journal, 37(3):409- 453, August 1998.]]

Digital Library

[25]

E. Morel and C. Renviose. Global optimization by supression of partial redundancies. CACM, 22(2):96-103, 1979.]]

Digital Library

[26]

Frank Mueller and David B. Whalley. Avoiding conditional branches by code replication. In ACM SIGPLAN Conference on Programming Language Design and Implementation, volume 30 of ACM SIGPLAN Notices, pages 56-66. ACM SIG- PLAN, ACM Press, June 1995.]]

Digital Library

[27]

George C. Necula. Compiling with Proofs. PhD thesis, Carnegie Mellon University, October 1998. Available as Technical Report CMU-CS-98-154.]]

Digital Library

[28]

G.C. Necula and P. Lee. The design and implementation of a certifying compiler. In Proceedings of the 1998 ACM SIG- PLAN Conference on Prgramming Language Design and Implementation (PLDI), pages 333-344, 1998.]]

Digital Library

[29]

Jason R.C. Patterson. Accurate static branch prediction by value range propagation, pages 67-78, June 1995. Proceedings of the 1995 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI).]]

Digital Library

[30]

V.R. Pratt. Two easy theories whose combinantion is hard. Technical report, Massachusetts Institute of Technology, 1977.]]

[31]

G. Ramalingam. Bounded incremental computation, volume 1089 of Lecture Notes in Computer Science. Springer-Verlag Inc., New York, NY, USA, 1996.]]

Digital Library

[32]

G. Ramalingam and Thomas Reps. An incremental algorithm for a generalization of the shortest-path problem. Journal of Algorithms, 21 (2):267-305, September 1996.]]

Digital Library

[33]

Radu Rugina and Martin Rinard. Automatic parallelization of divide and conquer algorithms. In Proceedings of the ACM SIGPLAN 1999 Symposium on Principles and Practice of Parallel Programming, Atlanta, GA, May 1999. ACM SIGPLAN.]]

Digital Library

[34]

Robert Shostak. Deciding Linear Inequalities by Computing Loop Residues. Journal of the Association for Computing Machinery, 28(4), 1981.]]

Digital Library

[35]

Norihisa Suzuki and Kiyoshi Ishihata. Implementation of an array bound checker. In Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, pages 132-143, Los Angeles, California, January 17-19, 1977. ACM SIGACT-SIGPLAN.]]

Digital Library

[36]

V. Sarkar and K. Knobe. Enabling sparse constant propagation of array elements via array SSA form. Lecture Notes in Computer Science, 1503:33-40, 1998.]]

[37]

Mooly Sagiv, Thomas Reps, and Susan Horwitz. Precise interprocedural dataflow analysis with applications to constant propagation. Theoretical Computer Science, 167(1-2):131- 170, 1996.]]

Digital Library

[38]

Just-In-Time Compilation. http://www, symantec.com/ cafe/analysis 1 .html#jitcomp.]]

[39]

Zhichen Xu, Barton Miller, and Thomas Reps. Safety checking of machine code. In Proceedings of the ACM SIGPLAN '00 Conf. on Progr. Language Design and Implementation, page to appear, jun 2000.]]

Digital Library

[40]

Hongwei Xi and Frank Pfenning. Eliminating array bound checking through dependent types. ACM SIGPLAN Notices, 33(5):249-257, May 1998. Proceedings of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI).]]

Digital Library

Cited By

Popescu NXu ZApostolakis SAugust DLevy A(2021)Safer at any speed: automatic context-aware safety enhancement for RustProceedings of the ACM on Programming Languages10.1145/34854805:OOPSLA(1-23)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485480
Xue HVenkataramani GLan TGottschlich JCheung A(2018)Clone-hunter: accelerated bound checks elimination via binary code clone detectionProceedings of the 2nd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages10.1145/3211346.3211347(11-19)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3211346.3211347
Béra CMiranda EFelgentreff TDenker MDucasse S(2017)SistaProceedings of the 14th International Conference on Managed Languages and Runtimes10.1145/3132190.3132201(1-11)Online publication date: 27-Sep-2017
https://dl.acm.org/doi/10.1145/3132190.3132201
Show More Cited By

Index Terms

ABCD: eliminating array bounds checks on demand

Recommendations

ABCD: eliminating array bounds checks on demand
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

To guarantee typesafe execution, Java and other strongly typed languages require bounds checking of array accesses. Because array-bounds checks may raise exceptions, they block code motion of instructions with side effects, thus preventing many useful ...
Dermatological expert system implementing the ABCD rule of dermoscopy for skin disease identification
Highlights
- An improvised ABCD Rule of Dermoscopy is introduced to develop an expert system.
Abstract
Doctors and radiologists generally follow the standard ABCD rule of dermoscopy for differentiating the malignant and benign skin lesions. The estimation of the dermoscopic score by visual inspection only, may lead to the inaccurate ...
ABCD rule and pre-trained CNNs for melanoma diagnosis

Skin cancer is the most common type of cancer and represents more than half of cancer diagnoses. Melanoma is the least frequent among skin cancers, but it is the most serious, with high potential for metastasis and can lead to death. However, melanoma ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 35, Issue 5

May 2000

357 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/358438

Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ

Issue’s Table of Contents

PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation
August 2000
358 pages
ISBN:1581131992
DOI:10.1145/349299
Chairman:
Monica Lam

Copyright © 2000 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Published in SIGPLAN Volume 35, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

212
Total Citations
View Citations
2,601
Total Downloads

Downloads (Last 12 months)404
Downloads (Last 6 weeks)49

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Popescu NXu ZApostolakis SAugust DLevy A(2021)Safer at any speed: automatic context-aware safety enhancement for RustProceedings of the ACM on Programming Languages10.1145/34854805:OOPSLA(1-23)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485480
Xue HVenkataramani GLan TGottschlich JCheung A(2018)Clone-hunter: accelerated bound checks elimination via binary code clone detectionProceedings of the 2nd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages10.1145/3211346.3211347(11-19)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3211346.3211347
Béra CMiranda EFelgentreff TDenker MDucasse S(2017)SistaProceedings of the 14th International Conference on Managed Languages and Runtimes10.1145/3132190.3132201(1-11)Online publication date: 27-Sep-2017
https://dl.acm.org/doi/10.1145/3132190.3132201
Popov NCosenza BJuurlink BStogov DWu PHack S(2017)Static optimization in PHP 7Proceedings of the 26th International Conference on Compiler Construction10.1145/3033019.3033026(65-75)Online publication date: 5-Feb-2017
https://dl.acm.org/doi/10.1145/3033019.3033026
Xue HChen YYao FLi YLan TVenkataramani G(2017)SIMBER: Eliminating Redundant Memory Bound Checks via Statistical InferenceICT Systems Security and Privacy Protection10.1007/978-3-319-58469-0_28(413-426)Online publication date: 4-May-2017
https://doi.org/10.1007/978-3-319-58469-0_28
Gao FChen TWang YSitu LWang LLi XMei HLv JJin ZLi X(2016)CarrayboundProceedings of the 8th Asia-Pacific Symposium on Internetware10.1145/2993717.2993724(81-90)Online publication date: 18-Sep-2016
https://dl.acm.org/doi/10.1145/2993717.2993724
Nazaré HMaffra ISantos WBarbosa LGonnord LQuintão Pereira F(2014)Validation of memory accesses through symbolic analysesACM SIGPLAN Notices10.1145/2714064.266020549:10(791-809)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660205
Nguyen TKapur DWeimer WForrest S(2014)DIGACM Transactions on Software Engineering and Methodology10.1145/255678223:4(1-30)Online publication date: 5-Sep-2014
https://dl.acm.org/doi/10.1145/2556782
Rafael de Assis Costa INazaré Santos HRafael Alves PMagno Quintão Pereira F(2014)Just-in-time value specializationComputer Languages, Systems & Structures10.1016/j.cl.2013.11.00140:2(37-52)Online publication date: Jul-2014
https://doi.org/10.1016/j.cl.2013.11.001
Tavares ABoissinot BPereira FRastello F(2014)Parameterized Construction of Program Representations for Sparse Dataflow AnalysesCompiler Construction10.1007/978-3-642-54807-9_2(18-39)Online publication date: 2014
https://doi.org/10.1007/978-3-642-54807-9_2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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 Issue’s Table of Contents