Article

Free access

ABCD: eliminating array bounds checks on demand

Authors:

Rastislav Bodík,

Vivek SarkarAuthors Info & Claims

PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

Pages 321 - 333

https://doi.org/10.1145/349299.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

Stein BChang BSridharan M(2024)Interactive Abstract Interpretation with Demanded SummarizationACM Transactions on Programming Languages and Systems10.1145/364844146:1(1-40)Online publication date: 15-Feb-2024
https://dl.acm.org/doi/10.1145/3648441
McMichen TGreiner NZhong PSossai FPatel ACampanoni SGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444817
Nguyen TNguyen KDwyer M(2022)Using Symbolic States to Infer Numerical InvariantsIEEE Transactions on Software Engineering10.1109/TSE.2021.310696448:10(3877-3899)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TSE.2021.3106964
Show More Cited By

Index Terms

ABCD: eliminating array bounds checks on demand

Recommendations

ABCD: eliminating array bounds checks on demand

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 Conferences

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

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

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI00

Sponsor:

PLDI00: ACM SIGPLAN 2000 Conference on Programming Language and Design and Implementation

June 18 - 21, 2000

British Columbia, Vancouver, Canada

Acceptance Rates

PLDI '00 Paper Acceptance Rate 30 of 173 submissions, 17%;

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

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

Stein BChang BSridharan M(2024)Interactive Abstract Interpretation with Demanded SummarizationACM Transactions on Programming Languages and Systems10.1145/364844146:1(1-40)Online publication date: 15-Feb-2024
https://dl.acm.org/doi/10.1145/3648441
McMichen TGreiner NZhong PSossai FPatel ACampanoni SGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444817
Nguyen TNguyen KDwyer M(2022)Using Symbolic States to Infer Numerical InvariantsIEEE Transactions on Software Engineering10.1109/TSE.2021.310696448:10(3877-3899)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TSE.2021.3106964
Mirliaz SPichardie D(2022)A Flow-Insensitive-Complete Program RepresentationVerification, Model Checking, and Abstract Interpretation10.1007/978-3-030-94583-1_10(197-218)Online publication date: 14-Jan-2022
https://doi.org/10.1007/978-3-030-94583-1_10
Jung TRitter FHack S(2021)PICOACM Transactions on Architecture and Code Optimization10.1145/346043418:4(1-27)Online publication date: 17-Jul-2021
https://dl.acm.org/doi/10.1145/3460434
Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Reif MKübler FHelm DHermann BEichberg MMezini MKrishnan PReichenbach C(2020)TACAI: an intermediate representation based on abstract interpretationProceedings of the 9th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3394451.3397204(2-7)Online publication date: 15-Jun-2020
https://dl.acm.org/doi/10.1145/3394451.3397204
Rodrigues MGuimarães BPereira FKandemir MJimborean AMoseley T(2019)Generation of in-bounds inputs for arrays in memory-unsafe languagesProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314890(136-148)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314890
Nam MAkritidis PGreaves DBalenson D(2019)FRAMERProceedings of the 35th Annual Computer Security Applications Conference10.1145/3359789.3359799(612-626)Online publication date: 9-Dec-2019
https://dl.acm.org/doi/10.1145/3359789.3359799
Blackburn SSinger JXu H(2019)Design and analysis of field-logging write barriersProceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management10.1145/3315573.3329981(103-114)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3315573.3329981
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 Table of Contents