More Web Proxy on the site http://driver.im/

Article

Incrementalized pointer and escape analysis

Authors:

Frédéric Vivien,

Martin RinardAuthors Info & Claims

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

Pages 35 - 46

https://doi.org/10.1145/378795.378804

Published: 01 May 2001 Publication History

Abstract

We present a new pointer and escape analysis. Instead of analyzing the whole program, the algorithm incrementally analyzes only those parts of the program that may deliver useful results. An analysis policy monitors the analysis results to direct the incremental investment of analysis resources to those parts of the program that offer the highest expected optimization return.

Our experimental results show that almost all of the objects are allocated at a small number of allocation sites and that an incremental analysis of a small region of the program surrounding each site can deliver almost all of the benefit of a whole-program analysis. Our analysis policy is usually able to deliver this benefit at a fraction of the whole-program analysis cost.

References

[1]

O. Agesen. The cartesian product algorithm: Simple and precise type inference of parametric polymorphism. In Proceedings of the 9th European Conference onObject-Oriented Programming, Aarhus, Denmark, Aug. 1995.]]

Digital Library

[2]

G. Agrawal. Simultaneous demand-driven data-flow and call graph analysis. In Proceedings of the 1999 International Conference on Software Maintenance, Oxford, UK, Aug. 1999.]]

Digital Library

[3]

B. Blanchet. Escape analysis for object oriented languages. application to Java. In Proceedings of the 14th Annual Conference onObject-Oriented Programming Systems, Languages and Applications, Denver, CO, Nov. 1999.]]

Digital Library

[4]

H. Boehm and M. Weiser. Garbage collection in an uncooperative environment. Software|Practice and Experience, 18(9):807-820, Sept. 1988.]]

Digital Library

[5]

J. Bogda and U. Hoelzle. Removing unnecessary synchronization in Java. In Proceedings of the 14th Annual Conference onObject-Oriented Programming Systems, Languages and Applications, Denver, CO, Nov. 1999.]]

Digital Library

[6]

G. Bollella et al. The Real-Time Specification for Java. Addison-Wesley, Reading, Mass., 2000.]]

Digital Library

[7]

J. Choi, M. Gupta, M. Serrano, V. Sreedhar, and S. Midkiff. Escape analysis for Java. In Proceedings of the 14th Annual Conference on Object-Oriented Programming Systems, Languages and Applications, Denver, CO, Nov. 1999.]]

Digital Library

[8]

E. Duesterwald, R. Gupta, and M. Soffa. A practical framework for demand-driven interprocedural data ow analysis. ACM Transactions on Programming Languages and Systems, 19(6):992-1030, Nov. 1997.]]

Digital Library

[9]

S. Guyer and C. Lin. Optimizing the use of high performance libraries. In Proceedings of the Thirteenth Workshop on Languages and Compilers for Parallel Computing, Yorktown Heights, NY, Aug. 2000.]]

Digital Library

[10]

Y. Lin and D. Padua. Demand-driven interprocedural array property analysis. In Proceedings of the Twelfth Workshop on Languages and Compilers for Parallel Computing, La Jolla, CA, Aug. 1999.]]

Digital Library

[11]

T. Reps, S. Horowitz, and M. Sagiv. Demand interprocedural data ow analysis. In Proceedings of the ACM SIGSOFT 95 Symposium on the Foundations of Software Engineering, Oct. 1995.]]

Digital Library

[12]

A. Rountev and B. Ryder. Points-to and side-effect analyses for programs built with precompiled libraries. In Proceedingsof CC 2001:International Conference on Compiler Construction, Genoa, Italy, Apr. 2001.]]

Digital Library

[13]

A. Rountev, B. Ryder, and W. Landi. Data-flow analysis of program fragments. In Proceedings of the ACM SIGSOFT 99 Symposium on the Foundations of Software Engineering, Toulouse, France, Sept. 1999.]]

Digital Library

[14]

E. Ruf. Effective synchronization removal for Java. In Proceedings of the SIGPLAN '00 Conference on Program Language Design and Implementation, Vancouver, Canada, June 2000.]]

Digital Library

[15]

R. Rugina and M. Rinard. Design-directed compilation. In Proceedings of CC 2001: International Conference on Compiler Construction, Genoa, Italy, Apr. 2001.]]

[16]

J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In Proceedings of the 14th Annual Conference on Object-Oriented Programming Systems, Languages and Applications, Denver, CO, Nov. 1999.]]

Digital Library

[17]

J. Yur, B. Ryder, and W. Landi. Incremental algorithms and empirical comparison for flow- and context-sensitive pointer aliasing analysis. In Proceedings of the 21st International conference on Software Engineering, Los Angeles, CA, May 1999.]]

Digital Library

Cited By

Anand AThakur M(2024)Partial program analysis for staged compilation systemsFormal Methods in System Design10.1007/s10703-024-00458-xOnline publication date: 13-Jun-2024
https://doi.org/10.1007/s10703-024-00458-x
Anand AThakur M(2022)Principles of Staged Static+Dynamic Partial AnalysisStatic Analysis10.1007/978-3-031-22308-2_4(44-73)Online publication date: 2-Dec-2022
https://doi.org/10.1007/978-3-031-22308-2_4
Dann AHermann BBodden E(2021)ModGuard : Identifying Integrity & Confidentiality Violations in Java ModulesIEEE Transactions on Software Engineering10.1109/TSE.2019.293133147:8(1656-1667)Online publication date: 1-Aug-2021
https://doi.org/10.1109/TSE.2019.2931331
Show More Cited By

Recommendations

Incrementalized pointer and escape analysis

We present a new pointer and escape analysis. Instead of analyzing the whole program, the algorithm incrementally analyzes only those parts of the program that may deliver useful results. An analysis policy monitors the analysis results to direct the ...
Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Practical pointer aliasing analysis

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

ACM SIGPLAN Notices Volume 36, Issue 5
May 2001
330 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/381694
Editors:
Cindy Norris,
James B. Bergin
Issue’s Table of Contents

Copyright © 2001 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 May 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI01

Sponsor:

SIGPLAN

PLDI01: ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation

Utah, Snowbird, USA

Acceptance Rates

PLDI '01 Paper Acceptance Rate 30 of 144 submissions, 21%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

82
Total Citations
View Citations
681
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Anand AThakur M(2024)Partial program analysis for staged compilation systemsFormal Methods in System Design10.1007/s10703-024-00458-xOnline publication date: 13-Jun-2024
https://doi.org/10.1007/s10703-024-00458-x
Anand AThakur M(2022)Principles of Staged Static+Dynamic Partial AnalysisStatic Analysis10.1007/978-3-031-22308-2_4(44-73)Online publication date: 2-Dec-2022
https://doi.org/10.1007/978-3-031-22308-2_4
Dann AHermann BBodden E(2021)ModGuard : Identifying Integrity & Confidentiality Violations in Java ModulesIEEE Transactions on Software Engineering10.1109/TSE.2019.293133147:8(1656-1667)Online publication date: 1-Aug-2021
https://doi.org/10.1109/TSE.2019.2931331
Thakur MNandivada V(2019)PYEACM Transactions on Programming Languages and Systems10.1145/333779441:3(1-37)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3337794
Doeraene SSchlatter T(2016)Parallel incremental whole-program optimizations for Scala.jsACM SIGPLAN Notices10.1145/3022671.298401351:10(59-73)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/3022671.2984013
Doeraene SSchlatter TVisser ESmaragdakis Y(2016)Parallel incremental whole-program optimizations for Scala.jsProceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2983990.2984013(59-73)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2983990.2984013
Kanvar VKhedker U(2016)Heap Abstractions for Static AnalysisACM Computing Surveys10.1145/293109849:2(1-47)Online publication date: 30-Jun-2016
https://dl.acm.org/doi/10.1145/2931098
Gu RJin GSong LZhu LLu SDi Nitto EHarman MHeymans P(2015)What change history tells us about thread synchronizationProceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering10.1145/2786805.2786815(426-438)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2786805.2786815
Chen YShi QMiao W(2015)Incremental Points-to Analysis for Java via Edit PropagationStructured Object-Oriented Formal Language and Method10.1007/978-3-319-17404-4_11(164-178)Online publication date: 17-Apr-2015
https://doi.org/10.1007/978-3-319-17404-4_11
Ratnakar BNasre. R(2014)Push-pull constraint graph for efficient points-to analysisACM SIGPLAN Notices10.1145/2775049.260298949:11(25-33)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2775049.2602989
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents