Article

Practical and Accurate Low-Level Pointer Analysis

Authors:

Matthew J. Bridges,

Spyridon Triantafyllis,

Guilherme Ottoni,

Easwaran Raman,

David I. AugustAuthors Info & Claims

CGO '05: Proceedings of the international symposium on Code generation and optimization

Pages 291 - 302

https://doi.org/10.1109/CGO.2005.27

Published: 20 March 2005 Publication History

Abstract

Pointer analysis is traditionally performed once, early in the compilation process, upon an intermediate representation (IR) with source-code semantics. However, performing pointer analysis only once at this level imposes a phase-ordering constraint, causing alias information to become stale after subsequent code transformations. Moreover, high-level pointer analysis cannot be used at link time or run time, where the source code is unavailable. This paper advocates performing pointer analysis on a low-level intermediate representation. We present the first context-sensitive and partially flow-sensitive points-to analysis designed to operate at the assembly level. As we will demonstrate, low-level pointer analysis can be as accurate as high-level analysis. Additionally, our low-level pointer analysis also enables a quantitative comparison of propagating high-level pointer analysis results through subsequent code transformations, versus recomputing them at the low level. We show that, for C programs, the former practice is considerably less accurate than the latter.

References

[1]

{1} W. W. Hwu, S. A. Mahlke, W. Y. Chen, P. P. Chang, N. J. Warter, R. A. Bringmann, R. G. Ouellette, R. E. Hank, T. Kiyohara, G. E. Haab, J. G. Holm, and D. M. Lavery, "The superblock: An effective technique for VLIW and superscalar compilation," The Journal of Supercomputing, vol. 7, pp. 229-248, January 1993.

Digital Library

[2]

{2} B.-C. Cheng and W.W. Hwu, "Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation," in ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 57-69, 2000.

Digital Library

[3]

{3} M. Hind, "Pointer analysis: Haven't we solved this problem yet?," in 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'01), 2001.

Digital Library

[4]

{4} R. P. Wilson and M. S. Lam, "Efficient context-sensitive pointer analysis for C programs," in Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pp. 1-12, June 1995.

Digital Library

[5]

{5} B. Steensgaard, "Points-to analysis by type inference in programs with structures and unions," in Lecture Notes in Computer Science, 1060 (T. Gyimothy, ed.), pp. 136-150, Springer-Verlag, 1996. Proceedings from the International Conference on Compiler Construction.

Digital Library

[6]

{6} R. Chatterjee, B. G. Ryder, and W. A. Landi, "Relevant context inference," in Proceedings of the ACM Symposium on Principles of Programming Languages, pp. 133-146, January 1999.

Digital Library

[7]

{7} S. Debray, R. Muth, and M. Weippert, "Alias analysis of executable code," in Proceedings of the ACM Symposium on Principles of Programming Languages, January 1998.

Digital Library

[8]

{8} G. Balakrishnan and T. Reps, "Analyzing memory accesses in x86 executables," in Proceedings of the 13th International Conference on Compiler Construction, pp. 5-23, 2004.

[9]

{9} B. Steensgaard, "Points-to analysis in almost linear time," in Proceedings of the ACM Symposium on Principles of Programming Languages , pp. 32-41, January 1996.

Digital Library

[10]

{10} W. Landi and B. G. Ryder, "A safe approximate algorithm for interprocedural pointer aliasing," in Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation , pp. 235-248, June 1992.

Digital Library

[11]

{11} L. O. Andersen, "Program analysis and specialization for the C programming language," May 1994.

[12]

{12} M. Emami, R. Ghiya, and L. J. Hendren, "Context-sensitive interprocedural points-to analysis in the presence of function pointers," in Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pp. 242-256, June 1994.

Digital Library

[13]

{13} A. Deutsch, "A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations," in Proceedings of the 1992 International Conference on Computer Languages , pp. 2-13, April 1992.

[14]

{14} M. Sagiv, T. Reps, and R.Wilhelm, "Solving shape-analysis problems in languages with destructive updating," in Proceedings of the ACM 23rd SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization (Dynamo '00), January 1996.

Digital Library

[15]

{15} M. Hind and A. Pioli, "Which pointer analysis should I use?," in Proceedings of ACM SIGSOFT International Symposium on Software Testing and Analysis, August 2000.

Digital Library

[16]

{16} A. Deutsch, "Interprocedural may-alias analysis for pointers: Beyond k-limiting," in Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pp. 230-241, June 1994.

Digital Library

[17]

{17} P. P. Chang, S. A. Mahlke,W. Y. Chen, N. J.Warter, and W.W. Hwu, "IMPACT: An architectural framework for multiple-instruction-issue processors," in Proceedings of the 18th International Symposium on Computer Architecture, pp. 266-275, May 1991.

Digital Library

Cited By

He DXie DWang YYou WLiang BHuang JShi WZhang ZZhang XChristakis MPradel M(2024)Define-Use Guided Path Exploration for Better Forced ExecutionProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652128(287-299)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652128
Wanninger NMcMichen TCampanoni SDinda PTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Getting a Handle on Unmanaged MemoryProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651326(448-463)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651326
McMichen TGreiner NZhong PSossai FPatel ACampanoni SGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444817
Show More Cited By

Index Terms

Practical and Accurate Low-Level Pointer Analysis
1. General and reference
  1. Cross-computing tools and techniques
    1. Measurement
    2. Performance
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Operational analysis
  2. Software notations and tools
    1. Compilers

Recommendations

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
Demand-driven pointer analysis

Known algorithms for pointer analysis are “global” in the sense that they perform an exhaustive analysis of a program or program component. In this paper we introduce a demand-driven approach for pointer analysis. Specifically, we describe a demand-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '05: Proceedings of the international symposium on Code generation and optimization

March 2005

313 pages

ISBN:076952298X

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 20 March 2005

Check for updates

Qualifiers

Article

Conference

CGO05

Sponsor:

CGO05: 3rd Annual IEEE / ACM International Symposium on Code Generation and Optimization

March 20 - 23, 2005

Acceptance Rates

CGO '05 Paper Acceptance Rate 26 of 75 submissions, 35%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
413
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

He DXie DWang YYou WLiang BHuang JShi WZhang ZZhang XChristakis MPradel M(2024)Define-Use Guided Path Exploration for Better Forced ExecutionProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652128(287-299)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652128
Wanninger NMcMichen TCampanoni SDinda PTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Getting a Handle on Unmanaged MemoryProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651326(448-463)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651326
McMichen TGreiner NZhong PSossai FPatel ACampanoni SGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Representing Data Collections in an SSA FormProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444817(308-321)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444817
Cheng KZheng YLiu TGuan LLiu PLi HZhu HYe KSun LJust RFraser G(2023)Detecting Vulnerabilities in Linux-Based Embedded Firmware with SSE-Based On-Demand Alias AnalysisProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598062(360-372)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598062
Pei KShe DWang MGeng SXuan ZDavid YYang JJana SRay BRoychoudhury ACadar CKim M(2022)NeuDep: neural binary memory dependence analysisProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3549147(747-759)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3549147
Licker NJones T(2020)Duplo: a framework for OCaml post-link optimisationProceedings of the ACM on Programming Languages10.1145/34089804:ICFP(1-29)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408980
Suchy BCampanoni SHardavellas NDinda PDonaldson ATorlak E(2020)CARAT: a case for virtual memory through compiler- and runtime-based address translationProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385987(329-345)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3385987
Katz OEl-Yaniv RYahav E(2016)Estimating types in binaries using predictive modelingACM SIGPLAN Notices10.1145/2914770.283767451:1(313-326)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2914770.2837674
Anand KElwazeer KKotha ASmithson MBarua RKeromytis A(2016)A Stack Memory Abstraction and Symbolic Analysis Framework for ExecutablesACM Transactions on Software Engineering and Methodology10.1145/289751125:2(1-38)Online publication date: 27-Apr-2016
https://dl.acm.org/doi/10.1145/2897511
Murphy NJones TMullins RCampanoni SZaks AHermenegildo M(2016)Performance implications of transient loop-carried data dependences in automatically parallelized loopsProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2892214(23-33)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2892208.2892214
Show More Cited By

View Options

Get Access

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