article

Related field analysis

Authors:

Aneesh Aggarwal,

Keith H. RandallAuthors Info & Claims

ACM SIGPLAN Notices, Volume 36, Issue 5

Pages 214 - 220

https://doi.org/10.1145/381694.378850

Published: 01 May 2001 Publication History

Get Access

Abstract

We present an extension of field analysis (sec [4]) called related field analysis which is a general technique for proving relationships between two or more fields of an object. We demonstrate the feasibility and applicability of related field analysis by applying it to the problem of removing array bounds checks. For array bounds check removal, we define a pair of related fields to be an integer field and an array field for which the integer field has a known relationship to the length of the array. This related field information can then be used to remove array bounds checks from accesses to the array field. Our results show that related field analysis can remove an average of 50% of the dynamic array bounds checks on a wide range of applications.

We describe the implementation of related field analysis in the Swift optimizing compiler for Java, as well as the optimizations that exploit the results of related field analysis.

References

[1]

R. Bodik, R. Gupta, and V. Sarkar. ABCD: Eliminating Array Bounds Checks on Demand. In Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation (PLDI), pages 321-333, June 2000.

Digital Library

Google Scholar

[2]

Compaq Computer Corporation. Compaq Fast Virtual Machine V1.2.2-4 for Alpha. At URL http://www. compaq.com/java.

Google Scholar

[3]

D. L. Detlefs, K. R. M. Leino, G. Nelson, and J. B. Saxe. Extended Static Checking. Technical Report 159, Compaq, 1998.

Google Scholar

[4]

S. Ghemawat, K. H. Randall, and D. J. Scales. Field Analysis: Getting Useful and Low-cost Interprocedural Information. In Proceedings of the ACMSIGPLAN '00 Conference on Programming Language Design and Implementation (PLDI), pages 334-344, June 2000.

Digital Library

Google Scholar

[5]

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

Digital Library

Google Scholar

[6]

P. Kolte and M. Wolfe. Elimination of Redundant Array Subscript Range Checks. In Proceedings of the SIGPLAN '95 Conference on Program Language Design and Implementation, June 1995.

Digital Library

Google Scholar

[7]

V. Markstein, J. Cocke, and P. Markstein. Optimization of Range Checking. In Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, June 1982.

Digital Library

Google Scholar

[8]

G. C. Necula. Compiling with Proofs. PhD thesis, Carnegie Mellon University, Oct. 1998. Available as tech report CMU- CS-98-154.

Digital Library

Google Scholar

[9]

J. R. Patterson. Accurate Static Branch Prediction by Value Range Propagation. In Proceedings of the SIGPLAN '95 Conference on Program Language Design and Implementation, pages 67-78, June 1995.

Digital Library

Google Scholar

[10]

R. Rugina and M. Rinard. Symbolic Bounds Analysis of Pointers, Array Indices, and Accessed Memory Regions. In Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation (PLDI), pages 182-195, June 2000.

Digital Library

Google Scholar

[11]

D. J. Scales, K. H. Randall, S. Ghemawat, and J. Dean. The Swift Java Compiler: Design and Implementation. Technical Report 2000/2, Compaq Western Research Laboratory, Apr. 2000.

Google Scholar

[12]

N. Suzuki and K. Ishihata. Implementation of an array bound checker. In Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, pages 132- 143, Jan. 1977.

Digital Library

Google Scholar

[13]

Z. Xu, B. P. Miller, and T. Reps. Safety Checking of Machine Code. In Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation (PLDI), pages 70-82, June 2000.

Digital Library

Google Scholar

Cited By

View all

Joyner MBudimlić ZSarkar V(2011)Subregion Analysis and Bounds Check Elimination for High Level ArraysCompiler Construction10.1007/978-3-642-19861-8_14(246-265)Online publication date: 2011
https://doi.org/10.1007/978-3-642-19861-8_14
Logozzo FCortesi A(2005)Abstract Interpretation and Object-oriented ProgrammingElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2005.01.024131(75-84)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.entcs.2005.01.024
Joyner MBudimlić ZSarkar V(2011)Subregion analysis and bounds check elimination for high level arraysProceedings of the 20th international conference on Compiler construction: part of the joint European conferences on theory and practice of software10.5555/1987237.1987256(246-265)Online publication date: 26-Mar-2011
https://dl.acm.org/doi/10.5555/1987237.1987256
Show More Cited By

Index Terms

Related field analysis
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types

Recommendations

Related field analysis
PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation

We present an extension of field analysis (sec [4]) called related field analysis which is a general technique for proving relationships between two or more fields of an object. We demonstrate the feasibility and applicability of related field analysis ...
CRB analysis of planar antenna arrays for optimizing near-field source localization

This paper focuses on the Cramér Rao bound (CRB) of the azimuth, elevation and range with planar arrays for narrowband near-field source localization, using the exact expression of the time delay. Specifically, the aim of this paper is twofold. First, ...
Performance analysis of higher order ESPRIT for localization of near-field sources

Most existing array processing techniques for estimating the directions of arrival (DOAs) or signal copy rely heavily on the plane-wave assumption of far-field sources. When the sources are located relatively close to the array, these techniques may no ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 36, Issue 5

May 2001

330 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/381694

Issue’s Table of Contents

PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation
June 2001
331 pages
ISBN:1581134142
DOI:10.1145/378795
Chairmen:
Michael Burke
IBM T.J. Watson Research Center
,
Mary Lou Soffa
Univ. of Pittsburgh

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 2001

Published in SIGPLAN Volume 36, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
372
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Joyner MBudimlić ZSarkar V(2011)Subregion Analysis and Bounds Check Elimination for High Level ArraysCompiler Construction10.1007/978-3-642-19861-8_14(246-265)Online publication date: 2011
https://doi.org/10.1007/978-3-642-19861-8_14
Logozzo FCortesi A(2005)Abstract Interpretation and Object-oriented ProgrammingElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2005.01.024131(75-84)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.entcs.2005.01.024
Joyner MBudimlić ZSarkar V(2011)Subregion analysis and bounds check elimination for high level arraysProceedings of the 20th international conference on Compiler construction: part of the joint European conferences on theory and practice of software10.5555/1987237.1987256(246-265)Online publication date: 26-Mar-2011
https://dl.acm.org/doi/10.5555/1987237.1987256
Joyner MBudimlić ZSarkar V(2011)Subregion Analysis and Bounds Check Elimination for High Level ArraysCompiler Construction10.1007/978-3-642-19861-8_14(246-265)Online publication date: 2011
https://doi.org/10.1007/978-3-642-19861-8_14
Ghose SGilgeous LDudnik PAggarwal AWaxman CBenini LDe Micheli GAl-Hashimi BMueller W(2009)Architectural support for low overhead detection of memory violationsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874782(652-657)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874782
Ghose SGilgeous LDudnik PAggarwal AWaxman C(2009)Architectural support for low overhead detection of memory violations2009 Design, Automation & Test in Europe Conference & Exhibition10.1109/DATE.2009.5090747(652-657)Online publication date: Apr-2009
https://doi.org/10.1109/DATE.2009.5090747
Logozzo F(2009)Class invariants as abstract interpretation of trace semanticsComputer Languages, Systems and Structures10.1016/j.cl.2005.01.00135:2(100-142)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.cl.2005.01.001
Logozzo F(2007)CibaiProceedings of the 8th international conference on Verification, model checking, and abstract interpretation10.5555/1763048.1763079(283-298)Online publication date: 14-Jan-2007
https://dl.acm.org/doi/10.5555/1763048.1763079
Rinetzky NPoetzsch-Heffter ARamalingam GSagiv MYahav E(2007)Modular shape analysis for dynamically encapsulated programsProceedings of the 16th European Symposium on Programming10.5555/1762174.1762197(220-236)Online publication date: 24-Mar-2007
https://dl.acm.org/doi/10.5555/1762174.1762197
Heffner KTarditi DSmith M(2007)Extending Object-Oriented Optimizations for Concurrent Programs16th International Conference on Parallel Architecture and Compilation Techniques (PACT 2007)10.1109/PACT.2007.4336205(119-129)Online publication date: Sep-2007
https://doi.org/10.1109/PACT.2007.4336205
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

Related field analysis

CRB analysis of planar antenna arrays for optimizing near-field source localization

Performance analysis of higher order ESPRIT for localization of near-field sources