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

research-article

Symbolic range analysis of pointers

Authors:

Vitor Paisante,

Leonardo Barbosa,

Fernando Magno Quintão PereiraAuthors Info & Claims

CGO '16: Proceedings of the 2016 International Symposium on Code Generation and Optimization

Pages 171 - 181

https://doi.org/10.1145/2854038.2854050

Published: 29 February 2016 Publication History

Abstract

Alias analysis is one of the most fundamental techniques that compilers use to optimize languages with pointers. However, in spite of all the attention that this topic has received, the current state-of-the-art approaches inside compilers still face challenges regarding precision and speed. In particular, pointer arithmetic, a key feature in C and C++, is yet to be handled satisfactorily. This paper presents a new alias analysis algorithm to solve this problem. The key insight of our approach is to combine alias analysis with symbolic range analysis. This combination lets us disambiguate fields within arrays and structs, effectively achieving more precision than traditional algorithms. To validate our technique, we have implemented it on top of the LLVM compiler. Tests on a vast suite of benchmarks show that we can disambiguate several kinds of C idioms that current state-of-the-art analyses cannot deal with. In particular, we can disambiguate 1.35x more queries than the alias analysis currently available in LLVM. Furthermore, our analysis is very fast: we can go over one million assembly instructions in 10 seconds.

Supplementary Material

Auxiliary Archive (p171-paisante-s.zip)

Download
369.50 KB

References

[1]

A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison Wesley, 2006.

Digital Library

[2]

L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, 1994.

[3]

G. Balakrishnan and T. Reps. Analyzing memory accesses in x86 executables. In In CC, pages 5–23. Springer, 2004.

[4]

W. Blume and R. Eigenmann. Symbolic range propagation. In In IPPS, pages 357–363, 1994.

Digital Library

[5]

R. Bodik, R. Gupta, and V. Sarkar. ABCD: eliminating array bounds checks on demand. In In PLDI, pages 321–333. ACM, 2000.

Digital Library

[6]

J.-D. Choi, R. Cytron, and J. Ferrante. Automatic construction of sparse data flow evaluation graphs. In In POPL, pages 55– 66. ACM, 1991.

Digital Library

[7]

P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In In POPL, pages 238–252. ACM, 1977.

Digital Library

[8]

R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. TOPLAS, 13(4):451–490, 1991.

Digital Library

[9]

D. Grunwald, B. Zorn, and R. Henderson. Improving the cache locality of memory allocation. In In PLDI, pages 177– 186. ACM, 1993.

Digital Library

[10]

B. Hardekopf and C. Lin. The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In In PLDI, pages 290–299. ACM, 2007.

Digital Library

[11]

B. Hardekopf and C. Lin. Flow-sensitive pointer analysis for millions of lines of code. In In CGO, pages 265–280, 2011.

Digital Library

[12]

M. Hind. Pointer analysis: Haven’t we solved this problem yet? In In PASTE, pages 54–61. ACM, 2001.

Digital Library

[13]

N. D. Jones and S. S. Muchnick. A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In In POPL, pages 66–74. ACM, 1982.

Digital Library

[14]

C. Lattner and V. S. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In CGO, pages 75––88. IEEE, 2004.

Digital Library

[15]

H. Nazaré, I. Maffra, W. Santos, L. Barbosa, L. Gonnord, and F. M. Q. Pereira. Validation of memory accesses through symbolic analyses. In In OOPSLA, pages 791–809. ACM, 2014.

Digital Library

[16]

H. Oh, W. Lee, K. Heo, H. Yang, and K. Yi. Selective contextsensitivity guided by impact pre-analysis. In In PLDI, pages 475–484. ACM, 2014.

Digital Library

[17]

D. J. Pearce, P. H. J. Kelly, and C. Hankin. Efficient fieldsensitive pointer analysis for C. In In PASTE, pages 37–42, 2004.

Digital Library

[18]

F. M. Q. Pereira and D. Berlin. Wave propagation and deep propagation for pointer analysis. In In CGO, pages 126–135. IEEE, 2009.

Digital Library

[19]

R. Rugina and M. C. Rinard. Symbolic bounds analysis of pointers, array indices, and accessed memory regions. TOPLAS, 27(2):185–235, 2005.

Digital Library

[20]

B. G. Ryder, W. A. Landi, P. A. Stocks, S. Zhang, and R. Altucher. A schema for interprocedural modification side-effect analysis with pointer aliasing. ACM Trans. Program. Lang. Syst., 23(2):105–186, 2001.

Digital Library

[21]

L. Shang, X. Xie, and J. Xue. On-demand dynamic symmarybased points-to analysis. In In CGO, pages 264–274. ACM, 2012.

Digital Library

[22]

B. Steensgaard. Points-to analysis in almost linear time. In In POPL, pages 32–41, 1996.

Digital Library

[23]

A. L. C. Tavares, B. Boissinot, F. M. Q. Pereira, and F. Rastello. Parameterized construction of program representations for sparse dataflow analyses. In In Compiler Construction, pages 2–21. Springer, 2014.

[24]

M. Wolfe. High Performance Compilers for Parallel Computing. Adison-Wesley, 1st edition, 1996.

Digital Library

[25]

D. Yan, G. Xu, and A. Rountev. Demand-driven contextsensitive alias analysis for java. In In ISSTA, pages 155–165. ACM, 2011.

Digital Library

[26]

S. H. Yong and S. Horwitz. Pointer-range analysis. In In SAS, pages 133–148. Springer, 2004.

[27]

Q. Zhang, X. Xiao, C. Zhang, H. Yuan, and Z. Su. Efficient subcubic alias analysis for C. In In OOPSLA, pages 829–845. ACM, 2014.

Digital Library

[28]

Q. Zhao, R. Rabbah, and W.-F. Wong. Dynamic memory optimization using pool allocation and prefetching. SIGARCH Comput. Archit. News, 33(5):27–32, 2005.

Digital Library

Cited By

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
Chitre KKedia PPurandare R(2023)Rapid: Region-Based Pointer DisambiguationProceedings of the ACM on Programming Languages10.1145/36228597:OOPSLA2(1729-1757)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622859
Chitre KKedia PPurandare R(2022)The road not taken: exploring alias analysis based optimizations missed by the compilerProceedings of the ACM on Programming Languages10.1145/35633166:OOPSLA2(786-810)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563316
Show More Cited By

Index Terms

Symbolic range analysis of pointers
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages

Recommendations

Pointer disambiguation via strict inequalities
CGO '17: Proceedings of the 2017 International Symposium on Code Generation and Optimization

The design and implementation of static analyses that disambiguate pointers has been a focus of research since the early days of compiler construction. One of the challenges that arise in this context is the analysis of languages that support pointer ...
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-...
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. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '16: Proceedings of the 2016 International Symposium on Code Generation and Optimization

February 2016

283 pages

ISBN:9781450337786

DOI:10.1145/2854038

General Chair:
Bjoern Franke
University of Edinburgh, UK
,
Program Chairs:
Youfeng Wu
Intel, USA
,
Fabrice Rastello
Inria, France

Copyright © 2016 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: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 February 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CGO '16

Sponsor:

CGO '16: 14th Annual IEEE/ACM International Symposium on Code Generation and Optimization

March 12 - 18, 2016

Barcelona, Spain

Acceptance Rates

CGO '16 Paper Acceptance Rate 25 of 108 submissions, 23%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
341
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Chitre KKedia PPurandare R(2023)Rapid: Region-Based Pointer DisambiguationProceedings of the ACM on Programming Languages10.1145/36228597:OOPSLA2(1729-1757)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622859
Chitre KKedia PPurandare R(2022)The road not taken: exploring alias analysis based optimizations missed by the compilerProceedings of the ACM on Programming Languages10.1145/35633166:OOPSLA2(786-810)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563316
Soares LMagno FPereira QLee J(2021)Memory-safe elimination of side channelsProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370305(200-210)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370305
Chandrasekhar AChen GChen PChen WGu JGuo PKumar SLueh GMistry PPan WRaoux TTrifunovic KKandemir MJimborean AMoseley T(2019)IGC: the open source Intel graphics compilerProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314902(254-265)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314902
Chandrasekhar AChen GChen PChen WGu JGuo PKumar SLueh GMistry PPan WRaoux TTrifunovic K(2019)IGC: The Open Source Intel Graphics Compiler2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO.2019.8661189(254-265)Online publication date: Feb-2019
https://doi.org/10.1109/CGO.2019.8661189
Sui YFan XZhou HXue J(2018)Loop-Oriented Pointer Analysis for Automatic SIMD VectorizationACM Transactions on Embedded Computing Systems10.1145/316836417:2(1-31)Online publication date: 30-Jan-2018
https://dl.acm.org/doi/10.1145/3168364
Zhao BXu XLiu PLi YZhao RYahyapour R(2018)A Demand-Driven Pointer-Range Analysis Technique for Data Transmission Optimization2018 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Ubiquitous Computing & Communications, Big Data & Cloud Computing, Social Computing & Networking, Sustainable Computing & Communications (ISPA/IUCC/BDCloud/SocialCom/SustainCom)10.1109/BDCloud.2018.00088(557-564)Online publication date: Dec-2018
https://doi.org/10.1109/BDCloud.2018.00088
Maalej MPaisante VMagno Quinto Pereira FGonnord L(2018)Combining range and inequality information for pointer disambiguationScience of Computer Programming10.1016/j.scico.2017.10.014152:C(161-184)Online publication date: 15-Jan-2018
https://dl.acm.org/doi/10.1016/j.scico.2017.10.014
Maalej MPaisante VRamos PGonnord LPereira FReddi VSmith ATang L(2017)Pointer disambiguation via strict inequalitiesProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049848(134-147)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049848
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