Article

Symbolic pointer analysis revisited

Authors:

Silvian CalmanAuthors Info & Claims

PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation

Pages 145 - 157

https://doi.org/10.1145/996841.996860

Published: 09 June 2004 Publication History

Abstract

Pointer analysis is a critical problem in optimizing compiler, parallelizing compiler, software engineering and most recently, hardware synthesis. While recent efforts have suggested symbolic method, which uses Bryant's Binary Decision Diagram as an alternative to capture the point-to relation, no speed advantage has been demonstrated for context-insensitive analysis, and results for context-sensitive analysis are only preliminary.In this paper, we refine the concept of symbolic transfer function proposed earlier and establish a common framework for both context-insensitive and context-sensitive pointer analysis. With this framework, our transfer function of a procedure can abstract away the impact of its callers and callees, and represent its point-to information completely, compactly and canonically. In addition, we propose a symbolic representation of the invocation graph, which can otherwise be exponentially large. In contrast to the classical frameworks where context-sensitive point-to information of a procedure has to be obtained by the application of its transfer function exponentially many times, our method can obtain point-to information of all contexts in a single application. Our experimental evaluation on a wide range of C benchmarks indicates that our context-sensitive pointer analysis can be made almost as fast as its context-insensitive counterpart.

References

[1]

SPEC CPU2000 benchmarks. http://www.specbench.org/cpu2000/.]]

[2]

S. B. Akers. Binary decision diagrams. IEEE Transactions on Computer, C-27(6):509--516, June 1978.]]

Digital Library

[3]

O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, Computer Science Department, University of Copenhagen, 1994.]]

[4]

T. Ball and T. Millstein. Polymorphic predicate abstraction. Technical Report MSR-TR-2001-10, Microsoft Research, June 24, 2003.]]

[5]

M. Berndl, O. Lhoták, F. Qian, L. Hendren, and N. Umanee. Point-to analysis using BDD. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, June 2003.]]

Digital Library

[6]

R. E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computer, C-35(8):677--691, August 1986.]]

Digital Library

[7]

J. R. Burch, E. M. Clarke, and D. E. Long. Symbolic model checking with partitioned transition relations. In International Conference on Very Large Scale Integration, Edinburgh, Scotland, 1991.]]

[8]

J. R. Burch, E. M. Clarke, D. E. Long, K. L. McMillan, and D. L. Dill. Symbolic model checking for sequential circuit verification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, (13), 1994.]]

Digital Library

[9]

J. R. Burch, E. M. Clarke, K. L. McMillan, D. L. Dill, and L. J. Hwang. Symbolic model checking: 1020 states and beyond. In Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science, Washington, DC, 1990.]]

[10]

R. Chatterjee, B. G. Ryder, and W. A. Landi. Relevant context inference. In Proceedings of Symposium on Principles of Programming Languages, pages 133--146, 1999.]]

Digital Library

[11]

B.-C. Cheng and W.-M. W. Hwu. Modular interprocedural pointer analysis using access paths: Design implementation and evaluation. In Proceedings of SIGPLAN Conference on Programming Language Design and Implementation, pages 57--69, Vancouver, British Columbia, Canada, June 2000.]]

Digital Library

[12]

O. Coudert, C. Berthet, and J. C. Madre. A unified framework for the formal verification of sequential circuits. In Proceedings of the International Conference on Computer-Aided Design, pages 126--129, November 1990.]]

[13]

O. Coudert and J. C. Madre. Symbolic computation of the valid states of a sequential machine: Algorithms and discussion. In ACM Workshop on Formal Methods in VLSI Design, 1991.]]

[14]

M. Emami, R. Ghiya, and L. J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of SIGPLAN Conference on Programming Language Design and Implementation, pages 242--256, 1994.]]

Digital Library

[15]

M. Fähndrich, J. S. Foster, Z. Su, and A. Aiken. Partial online cycle elimination in inclusion constraint graphs. ACM SIGPLAN Notices, 33(5):85--96, 1998.]]

Digital Library

[16]

M. Fähndrich, J. Rehof, and M. Das. Scalable context-sensitive flow analysis using instantiation constraints. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 253--263, Vancouver, British Columbia, Canada, June 2000.]]

Digital Library

[17]

J. S. Foster, M. Fähndrich, and A. Aiken. Polymorphic versus monomorphic flow-insensitive points-to analysis for C. In Proceedings of Static Analysis Symposium, pages 175--198, June 2000.]]

Digital Library

[18]

D. Gajski. Principles of Digital Design. Prentice Hall, 1997.]]

Digital Library

[19]

N. Heintze and O. Tardieu. Ultra-fast aliasing analysis using CLA: A million lines of C code in a second. In Proceedings of SIGPLAN Conference on Programming Language Design and Implementation, pages 254--263, 2001.]]

Digital Library

[20]

M. Hind. Pointer analysis: Haven't we solved this problem yet. In ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE), June 2001.]]

Digital Library

[21]

M. Hind, M. Burke, P. Carini, and J.-D. Choi. Interprocedural pointer alias analysis. ACM Transactions on Programming Languages and Systems, 21(4):848--894, 1999.]]

Digital Library

[22]

M. Hind and A. Pioli. Assessing the effects of flow-sensitivity on pointer alias analyses. In Proceedings of Static Analysis Symposium, pages 57--81, 1998.]]

Digital Library

[23]

M. Hind and A. Pioli. Which pointer analysis should I use? In International Symposium on Software Testing and Analysis, pages 113--123, 2000.]]

Digital Library

[24]

W. Landi and B. Ryder. A safe approximate algorithm for inter-procedural pointer aliasing. In Proceedings of SIGPLAN Conference on Programming Language Design and Implementation, pages 235--248, June 1992.]]

Digital Library

[25]

C. Lee, M. Potkonjak, and W. H. Mangione-Smith. Mediabench: A tool for evaluating and synthesizing multimedia and communications systems. In Micro 30, 1997.]]

Digital Library

[26]

O. Lhoták and L. Hendren. Jedd: A BDD-based relational extension of Java. In Proceedings of SIGPLAN Conference on Programming Language Design and Implementation, June 2004.]]

Digital Library

[27]

D. Liang and M. J. Harrold. Efficient computation of parameterized pointer information for interprocedural analyses. In Proceedings of Static Analysis Symposium, pages 279--298, 2001.]]

Digital Library

[28]

A. Milanova, A. Rountev, and B. Ryder. Parameterized object-sensitivity for points-to and side-effect analysis for Java. In Proceedings of International Symposium on Software Testing and Analysis, pages 1--12, 2000.]]

Digital Library

[29]

I.-H. Moon, J. H. Kukula, K. Ravi, and F. Somenzi. To split or to conjoin: the question in image computation. In Design Automation Conference, pages 23--28, 2000.]]

Digital Library

[30]

A. Rountev and S. Chandra. Off-line variable substitution for scaling points-to analysis. ACM SIGPLAN Notices, 35(5):47--56, 2000.]]

Digital Library

[31]

E. Ruf. Context-insensitive alias analysis reconsidered. In Proceedings of SIGPLAN Conference on Programming Language Design and Implementation, pages 13--22, La Jolla, California, June 1995.]]

Digital Library

[32]

B. Ryder. Prolangs analysis framework. http://www.prolangs.rutgers.edu.]]

[33]

M. Sagiv, T. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. ACM Transactions on Programming Languages and Systems, 24(3):217--298, 2002.]]

Digital Library

[34]

M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, pages 189--234. Prentice Hall, 1981.]]

[35]

F. Somenzi. CUDD: Binary decision diagram package release. http://vlsi.Colorado.EDU/fabio/CUDD/cuddIntro.html, 1998.]]

[36]

B. Steensgaard. Points-to analysis in almost linear time. In Proceedings of Symposium on Principles of Programming Languages, pages 32--41, 1996.]]

Digital Library

[37]

R. Tarjan. Depth first search and linear graph algorithms. SIAM Journal of Computing, 1(2):146--160, 1972.]]

[38]

J. Whaley and M. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of SIGPLAN Conference on Programming Language Design and Implementation, June 2004.]]

Digital Library

[39]

R. Wilson and M. Lam. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 1--12, June 1995.]]

Digital Library

[40]

S. Zhang, B. G. Ryder, and W. Landi. Program decomposition for pointer aliasing: A step toward practical analyses. In Foundations of Software Engineering, pages 81--92, 1996.]]

Digital Library

[41]

J. Zhu. Symbolic pointer analysis. In Proceedings of the International Conference in Computer Aided Design, San Jose, November 2002.]]

Digital Library

Cited By

Barbar MSui Y(2021)Compacting points-to sets through object clusteringProceedings of the ACM on Programming Languages10.1145/34855475:OOPSLA(1-27)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485547
Tang WHu YFan GYao PWu RBai GWang PZhang CGrundy J(2021)TranscodeProceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE51524.2021.9678823(829-841)Online publication date: 15-Nov-2021
https://dl.acm.org/doi/10.1109/ASE51524.2021.9678823
Barbar MSui Y(2021)Hash Consed Points-To SetsStatic Analysis10.1007/978-3-030-88806-0_2(25-48)Online publication date: 13-Oct-2021
https://doi.org/10.1007/978-3-030-88806-0_2
Show More Cited By

Index Terms

Symbolic pointer analysis revisited
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages

Recommendations

Symbolic pointer analysis revisited
PLDI '04

Pointer analysis is a critical problem in optimizing compiler, parallelizing compiler, software engineering and most recently, hardware synthesis. While recent efforts have suggested symbolic method, which uses Bryant's Binary Decision Diagram as an ...
Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation

We present Paddle, a framework of BDD-based context-sensitive points-to and call graph analyses for Java, as well as client analyses that use their results. Paddle supports several variations of context-sensitive analyses, including call site strings ...
Semi-sparse flow-sensitive pointer analysis
POPL '09

Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation

June 2004

310 pages

ISBN:1581138075

DOI:10.1145/996841

General Chair:
William Pugh
University of Maryland, College Park
,
Program Chair:
Craig Chambers
University of Washington

ACM SIGPLAN Notices Volume 39, Issue 6
PLDI '04
May 2004
299 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/996893
Issue’s Table of Contents

Copyright © 2004 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: 09 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI04

Sponsor:

PLDI04: ACM SIGPLAN Conference on Programming Language Design and Implementation 2004

June 9 - 11, 2004

Washington DC, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

99
Total Citations
View Citations
702
Total Downloads

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

Reflects downloads up to 04 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Barbar MSui Y(2021)Compacting points-to sets through object clusteringProceedings of the ACM on Programming Languages10.1145/34855475:OOPSLA(1-27)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485547
Tang WHu YFan GYao PWu RBai GWang PZhang CGrundy J(2021)TranscodeProceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE51524.2021.9678823(829-841)Online publication date: 15-Nov-2021
https://dl.acm.org/doi/10.1109/ASE51524.2021.9678823
Barbar MSui Y(2021)Hash Consed Points-To SetsStatic Analysis10.1007/978-3-030-88806-0_2(25-48)Online publication date: 13-Oct-2021
https://doi.org/10.1007/978-3-030-88806-0_2
Thiessen RLhoták O(2017)Context transformations for pointer analysisACM SIGPLAN Notices10.1145/3140587.306235952:6(263-277)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062359
Thiessen RLhoták OCohen AVechev M(2017)Context transformations for pointer analysisProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062359(263-277)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062359
Ireland IAmaral JSilvera RCui S(2016)SafeTypeSoftware—Practice & Experience10.1002/spe.238846:11(1571-1588)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1002/spe.2388
Liu FLi BNasre R(2016)Efficient online cycle detection technique combining with Steensgaard points-to informationSoftware—Practice & Experience10.1002/spe.232946:5(601-623)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1002/spe.2329
Feng YWang XDillig IDillig T(2015)Bottom-Up Context-Sensitive Pointer Analysis for JavaProgramming Languages and Systems10.1007/978-3-319-26529-2_25(465-484)Online publication date: 9-Dec-2015
https://doi.org/10.1007/978-3-319-26529-2_25
Sun QChen YZhao J(2014)A constraint-weaving approach to points-to analysis for AspectJFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-013-3106-28:1(52-68)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s11704-013-3106-2
Mangal RNaik MYang H(2014)A Correspondence between Two Approaches to Interprocedural Analysis in the Presence of JoinProceedings of the 23rd European Symposium on Programming Languages and Systems - Volume 841010.1007/978-3-642-54833-8_27(513-533)Online publication date: 5-Apr-2014
https://dl.acm.org/doi/10.1007/978-3-642-54833-8_27
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.

Figures

Tables

Media

View Table of Conten