research-article

Level by level: making flow- and context-sensitive pointer analysis scalable for millions of lines of code

Authors:

Zhaoqing ZhangAuthors Info & Claims

CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization

Pages 218 - 229

https://doi.org/10.1145/1772954.1772985

Published: 24 April 2010 Publication History

Abstract

We present a practical and scalable method for flow- and context-sensitive (FSCS) pointer analysis for C programs. Our method analyzes the pointers in a program level by level in terms of their points-to levels, allowing the points-to relations of the pointers at a particular level to be discovered based on the points-to relations of the pointers at this level and higher levels. This level-by-level strategy can enhance the scalability of the FSCS pointer analysis in two fundamental ways, by enabling (1) fast and accurate flow-sensitive analysis on full sparse SSA form using a flow-insensitive algorithm and (2) fast and accurate context-sensitive analysis using a full transfer function and a meet function for each procedure.

Our level-by-level algorithm, LevPA, gives rises to (1) a precise and compact SSA representation for subsequent program analysis and optimization tasks and (2) a flow- and context-sensitive MAY/MUST mod (modification) set and read set for each procedure. Our preliminary results show that LevPA can analyze some programs with over a million lines of C code in minutes, faster than the state-of-the-art FSCS methods.

References

[1]

ANDERSEN, L. O. Program analysis and specialization for the c programming language, 1994.

[2]

BRYANT, R. E. Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35, 8 (1986), 677--691.

Digital Library

[3]

CHASE, D. R., WEGMAN, M., AND ZADECK, F. K. Analysis of pointers and structures. In PLDI '90: Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation (New York, NY, USA, 1990), ACM, pp. 296--310.

Digital Library

[4]

CHATTERJEE, R., RYDER, B. G., AND LANDI, W. A. Relevant context inference. In POPL '99: Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (NewYork, NY, USA, 1999), ACM, pp. 133--146.

Digital Library

[5]

CHENG, B.-C., AND HWU, W.-M. W. Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation. In PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation (NewYork, NY, USA, 2000), ACM, pp. 57--69.

Digital Library

[6]

CHOI, J.-D., BURKE, M., AND CARINI, P. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (New York, NY, USA, 1993), ACM, pp. 232--245.

Digital Library

[7]

CHOW, F. C., CHAN, S., LIU, S.-M., LO, R., AND STREICH, M. Effective representation of aliases and indirect memory operations in ssa form. In CC '96: Proceedings of the 6th International Conference on Compiler Construction (London, UK, 1996), Springer-Verlag, pp. 253--267.

Digital Library

[8]

CYTRON, R., FERRANTE, J., ROSEN, B. K., WEGMAN, M. N., AND ZADECK, K. F. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems 13 (1991), 451--490.

Digital Library

[9]

EMAMI, M., GHIYA, R., AND HENDREN, L. J. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation (New York, NY, USA, 1994), ACM, pp. 242--256.

Digital Library

[10]

HACKETT, B., AND AIKEN, A. How is aliasing used in systems software? In SIGSOFT '06/FSE-14: Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering (New York, NY, USA, 2006), ACM, pp. 69--80.

Digital Library

[11]

HARDEKOPF, B., AND LIN, C. Semi-sparse flow-sensitive pointer analysis. In POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (New York, NY, USA, 2009), ACM, pp. 226--238.

Digital Library

[12]

HASTI, R., AND HORWITZ, S. Using static single assignment form to improve flow-insensitive pointer analysis. In PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation (New York, NY, USA, 1998), ACM, pp. 97--105.

Digital Library

[13]

HIND, M., BURKE, M., CARINI, P., AND CHOI, J.-D. Interprocedural pointer alias analysis. ACM Trans. Program. Lang. Syst. 21, 4(1999), 848--894.

Digital Library

[14]

KAHLON, V. Bootstrapping: a technique for scalable flow and context-sensitive pointer alias analysis. In PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation (New York, NY, USA, 2008), ACM, pp. 249--259.

Digital Library

[15]

KANG, H.-G., AND HAN, T. A bottom-up pointer analysis using the update history. Inf. Softw. Technol. 51, 4 (2009), 691--707.

Digital Library

[16]

LANDI, W., AND RYDER, B. G. A safe approximate algorithm for interprocedural aliasing. SIGPLAN Not. 27, 7 (1992), 235--248.

Digital Library

[17]

LIVSHITS, V. B., AND LAM, M. S. Tracking pointers with path and context sensitivity for bug detection in c programs. In ESEC/FSE11: Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering (New York, NY, USA, 2003),ACM, pp. 317--326.

Digital Library

[18]

LUNDBERG, J., AND LÖWE, W. A scalable flow-sensitive points-to analysis. In Compiler Construction -- Advances and Applications, Festschrift on the occasion of the retirement of Prof. Dr. Dr. h.c. Gerhard Goos (2007), Springer Verlag. accepted.

[19]

NAEEM, N. A., AND LHOTAK, O. Efficient alias set analysis using ssa form. In ISMM '09: Proceedings of the 2009 international symposium on Memory management (New York, NY, USA, 2009), ACM, pp. 79--88.

Digital Library

[20]

RYDER, B. G., LANDI, W. A., STOCKS, P. A., ZHANG, S., AND ALTUCHER, R. A schema for interprocedural modification side-effect analysis with pointer aliasing. ACM Trans. Program. Lang. Syst. 23, 2 (2001), 105---186.

Digital Library

[21]

STEENSGAARD, B. Points-to analysis by type inference of programs with structures and unions. In CC '96: Proceedings of the 6th International Conference on Compiler Construction (London, UK, 1996), Springer-Verlag, pp. 136--150.

Digital Library

[22]

STEENSGAARD, B. Points-to analysis in almost linear time. In POPL'96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (New York, NY, USA, 1996), ACM, pp. 32--41.

Digital Library

[23]

TOK, T., GUYER, S., AND LIN, C. Efficient Flow-Sensitive Interprocedural Data-Flow Analysis in the Presence of Pointers. In Compiler construction: 15th international conference, CC 2006, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006, Vienna, Austria, March 30--31, 2006: proceedings(2006), Springer-Verlag New York Inc, p. 17.

Digital Library

[24]

WHALEY, J., AND LAM, M. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation (2004), ACM New York, NY, USA, pp. 131--144.

Digital Library

[25]

WILSON, R. P., AND LAM, M. S. Efficient context-sensitive pointer analysis for c programs. In PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation (New York, NY, USA, 1995), ACM, pp. 1--12.

Digital Library

[26]

YU, H., AND ZHANG, Z. An Aggressive field-sensitive unification-based pointer analysis. Chinese Journal of Computers 32, 9 (2009).

[27]

ZHENG, B., AND CHUNG YEW, P. A hierarchical approach to context-sensitive interprocedural alias analysis, 1999.

[28]

ZHU, J. Towards scalable flow and context sensitive pointer analysis. In DAC '05: Proceedings of the 42nd annual Design Automation Conference (New York, NY, USA, 2005), ACM, pp. 831--836.

Digital Library

Cited By

Li TBai JSui YHu S(2024)SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate AnalysisACM Transactions on Computer Systems10.1145/369525042:3-4(1-40)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3695250
Zou CHe DSui YXue J(2024)TIPS: Tracking Integer-Pointer Value Flows for C++ Member Function PointersProceedings of the ACM on Software Engineering10.1145/36607791:FSE(1609-1631)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660779
Cheng XWang JSui YRoychoudhury APaiva AAbreu RStorey M(2024)Precise Sparse Abstract Execution via Cross-Domain InteractionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639220(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639220
Show More Cited By

Index Terms

Level by level: making flow- and context-sensitive pointer analysis scalable for millions of lines of code
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
2. Theory of computation
  1. Semantics and reasoning
    1. Program semantics

Recommendations

Precise flow-insensitive may-alias analysis is NP-hard

Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. ...
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-...
Semi-sparse flow-sensitive pointer analysis
POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

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

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization

April 2010

300 pages

ISBN:9781605586359

DOI:10.1145/1772954

General Chairs:
Andreas Moshovos
University of Toronto
,
Greg Steffan
University of Toronto
,
Program Chairs:
Kim Hazelwood
University of Virginia
,
David Kaeli
Northeastern University

Copyright © 2010 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

In-Cooperation

IEEE CS uArch

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 April 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CGO '10

Sponsor:

CGO '10: 8th Annual IEEE/ ACM International Symposium on Code Generation and Optimization

April 24 - 28, 2010

Ontario, Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 312 of 1,061 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
810
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)9

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li TBai JSui YHu S(2024)SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate AnalysisACM Transactions on Computer Systems10.1145/369525042:3-4(1-40)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3695250
Zou CHe DSui YXue J(2024)TIPS: Tracking Integer-Pointer Value Flows for C++ Member Function PointersProceedings of the ACM on Software Engineering10.1145/36607791:FSE(1609-1631)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660779
Cheng XWang JSui YRoychoudhury APaiva AAbreu RStorey M(2024)Precise Sparse Abstract Execution via Cross-Domain InteractionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639220(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639220
Li HTan TLi YLu JMeng HCao LHuang YLi LGao LDi PLin LCui C(2024)Generic Sensitivity: Generics-Guided Context Sensitivity for Pointer AnalysisIEEE Transactions on Software Engineering10.1109/TSE.2024.337764550:5(1144-1162)Online publication date: May-2024
https://doi.org/10.1109/TSE.2024.3377645
Cai YZhang C(2023)A Cocktail Approach to Practical Call Graph ConstructionProceedings of the ACM on Programming Languages10.1145/36228337:OOPSLA2(1001-1033)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622833
Li HLu JMeng HCao LHuang YLi LGao LRoychoudhury ACadar CKim M(2022)Generic sensitivity: customizing context-sensitive pointer analysis for genericsProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3549122(1110-1121)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3549122
Suchy BGhosh SKersnar DChai SHuang ZNelson ACuevas MBernat AChaudhary GHardavellas NCampanoni SDinda PFalsafi BFerdman MLu SWenisch T(2022)CARAT CAKE: replacing paging via compiler/kernel cooperationProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507771(98-114)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507771
Li TBai JSui YHu SFalsafi BFerdman MLu SWenisch T(2022)Path-sensitive and alias-aware typestate analysis for detecting OS bugsProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507770(859-872)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507770
Park JLee HRyu S(2021)A Survey of Parametric Static AnalysisACM Computing Surveys10.1145/346445754:7(1-37)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3464457
Cai YYao PZhang CFreund SYahav E(2021)Canary: practical static detection of inter-thread value-flow bugsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454099(1126-1140)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454099
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