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

article

Ultra-fast aliasing analysis using CLA: a million lines of C code in a second

Authors:

Olivier TardieuAuthors Info & Claims

ACM SIGPLAN Notices, Volume 36, Issue 5

Pages 254 - 263

https://doi.org/10.1145/381694.378855

Published: 01 May 2001 Publication History

Abstract

We describe the design and implementation of a system for very fast points-to analysis. On code bases of about million lines of unpreprocessed C code, our system performs field-based Andersen-style points-to analysis in less than a second and uses less than 10MB of memory. Our two main contributions are a database-centric analysis architecture called compile-link-analyze (CLA), and a new algorithm for implementing dynamic transitive closure. Our points-to analysis system is built into a forward data-dependence analysis tool that is deployed within Lucent to help with consistent type modifications to large legacy C code bases.

References

[1]

A. Aiken, M. F. ahndrich, J. Foster, and Z. Su, "A Toolkit for Constructing Type- and Constraint-Based Program Analyses", TIC'98.]]

Digital Library

[2]

A. Aiken and E. Wimmers, "Solving Systems of Set Constraints", LICS, 1992.]]

[3]

A. Aiken and E. Wimmers, "Type Inclusion Constraints and Type Inference", ICFP, 1993.]]

Digital Library

[4]

L. Andersen, "Program Analysis and Specialization for the C Programming Language", PhD. thesis, DIKU report 94/19, 1994,]]

[5]

D. Atkinson and W. Griswold, "Effective Whole-Program Analysis in the Presence of Pointers", 1998 Symp. on the Foundations of Soft. Eng.]]

Digital Library

[6]

S. Chandra, N. Heintze, D. MacQueen, D. Oliva and M. Siff, "ckit: an extensible C frontend in ML",to be released as an SML/NJ library.]]

[7]

S. Chandra and T. Reps, "Physical Type Checking for C" PASTE, 1999.]]

Digital Library

[8]

M. Das, "Unification-Based Pointer Analysis with Directional Assignments" PLDI, 2000.]]

Digital Library

[9]

"Appendix D: Optimizing Techniques (MIPS-Based C Compiler)", Programmer's Guide: Digital UNIX Version 4.0, Digital Equipment Corporation, March 1996.]]

[10]

J. Foster, M. F.ahndrich and A. Aiken, "Flow-Insensitive Points-to Analysis with Term and Set Constraints" U. of California, Berkeley, UCB//CSD97964, 1997.]]

Digital Library

[11]

M. F.ahndrich, J. Foster, Z. Su and A. Aiken, "Partial Online Cycle Elimination in Inclusion Constraint Graphs" PLDI, 1998.]]

Digital Library

[12]

C. Flanagan and M. Felleisen, "Componential Set-Based Analysis" PLDI, 1997.]]

Digital Library

[13]

J. Foster, M. F. ahndrich and A. Aiken, "Polymorphic versus Monomorphic Flow-insensitive Points-to Analysis for C", SAS 2000.]]

Digital Library

[14]

N. Heintze, "Set Based Program Analysis", PhD thesis, Carnegie Mellon University, 1992.]]

Digital Library

[15]

N. Heintze, "Set-Based Analysis of ML Programs", LFP, 1994.]]

Digital Library

[16]

N. Heintze, "Analysis of Large Code Bases: The Compile-Link-Analyze Model" unpublished report, November 1999.]]

[17]

N. Heintze and J. Jaffar, "A decision procedure for a class of Herbrand set constraints" LICS, 1990.]]

[18]

N. Heintze and D. McAllester, "On the Cubic-Bottleneck of Subtyping and Flow Analysis" LICS, 1997.]]

Digital Library

[19]

"Programming Languages - C", ISO/IEC 9899:1990, Internation Standard, 1990.]]

[20]

D. McAllester, "On the Complexity Analysis of Static Analysis", SAS, 1999.]]

Digital Library

[21]

A. Rountev and S. Chandra, "Off-line Variable Substitution for Scaling Points-to Analysis", PLDI, 2000.]]

Digital Library

[22]

M. Shapiro and S. Horwitz, "Fast and Accurate Flow-Insensitive Points-To Analysis", POPL, 1997.]]

Digital Library

[23]

Z. Su, M. F. ahndrich, and A. Aiken, "Projection Merging: Reducing Redundancies in Inclusion Constraint Graphs", POPL, 2000.]]

Digital Library

[24]

B. Steensgaard, "Points-to Analysis in Almost Linear Time", POPL, 1996.]]

Digital Library

[25]

F. Tip, "Generation of Program Analysis Tools", Institute for Logic Language and Computation dissertation series, 1995-5, 1995.]]

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
Liu PLi YSwain BHuang JDwyer MDamian DZeller A(2022)PUSProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510075(1781-1792)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510075
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
Show More Cited By

Index Terms

Ultra-fast aliasing analysis using CLA: a million lines of C code in a second

Recommendations

Ultra-fast aliasing analysis using CLA: a million lines of C code in a second
PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation

We describe the design and implementation of a system for very fast points-to analysis. On code bases of about million lines of unpreprocessed C code, our system performs field-based Andersen-style points-to analysis in less than a second and uses less ...
Practical pointer aliasing analysis
Program decomposition for pointer aliasing: a step toward practical analyses

Pointer aliasing analysis is crucial to compile-time analyses for languages with general-purpose pointer usage (such as C), but many aliasing methods have proven quite costly. We present a technique that partitions the statements of a program to allow ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

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

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]

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

218
Total Citations
View Citations
1,146
Total Downloads

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

Reflects downloads up to 10 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
Liu PLi YSwain BHuang JDwyer MDamian DZeller A(2022)PUSProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510075(1781-1792)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510075
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
Suzuki KKubota TKono K(2020)Detecting Struct Member-Related Memory Leaks Using Error Code Analysis in Linux Kernel2020 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)10.1109/ISSREW51248.2020.00097(329-335)Online publication date: Oct-2020
https://doi.org/10.1109/ISSREW51248.2020.00097
Pagani FBalzarotti DHeninger NTraynor P(2019)Back to the whiteboardProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361460(1751-1768)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361460
Lei YSui Y(2019)Fast and Precise Handling of Positive Weight Cycles for Field-Sensitive Pointer AnalysisStatic Analysis10.1007/978-3-030-32304-2_3(27-47)Online publication date: 2-Oct-2019
https://doi.org/10.1007/978-3-030-32304-2_3
Aleen FZakharin VKrishaniyer RGupta GKreitzer DLin CPalermo GFeo JTumeo AFranke H(2016)Automated compiler optimization of multiple vector loads/storesProceedings of the ACM International Conference on Computing Frontiers10.1145/2903150.2903169(82-91)Online publication date: 16-May-2016
https://dl.acm.org/doi/10.1145/2903150.2903169
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
Zeng JFu YLin Z(2015)PEMUACM SIGPLAN Notices10.1145/2817817.273120150:7(147-160)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2817817.2731201
Oh JKwon JPark HMoon S(2015)Migration of Web Applications with Seamless ExecutionACM SIGPLAN Notices10.1145/2817817.273119750:7(173-185)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2817817.2731197
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 Issue’s Table of Contents