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

research-article

Parallel inclusion-based points-to analysis

Authors:

Mario Méndez-Lojo,

Augustine Mathew,

Keshav PingaliAuthors Info & Claims

ACM SIGPLAN Notices, Volume 45, Issue 10

Pages 428 - 443

https://doi.org/10.1145/1932682.1869495

Published: 17 October 2010 Publication History

Abstract

Inclusion-based points-to analysis provides a good trade-off between precision of results and speed of analysis, and it has been incorporated into several production compilers including gcc. There is an extensive literature on how to speed up this algorithm using heuristics such as detecting and collapsing cycles of pointer-equivalent variables. This paper describes a complementary approach based on exploiting parallelism. Our implementation exploits two key insights. First, we show that inclusion-based points-to analysis can be formulated entirely in terms of graphs and graph rewrite rules. This exposes the amorphous data-parallelism in this algorithm and makes it easier to develop a parallel implementation. Second, we show that this graph-theoretic formulation reveals certain key properties of the algorithm that can be exploited to obtain an efficient parallel implementation. Our parallel implementation achieves a scaling of up to 3x on a 8-core machine for a suite of ten large C programs. For all but the smallest benchmarks, the parallel analysis outperforms a state-of-the-art, highly optimized, serial implementation of the same algorithm. To the best of our knowledge, this is the first parallel implementation of a points-to analysis.

References

[1]

}}Galois website. http://iss.ices.utexas.edu/galois/.

[2]

}}A. Aho, R. Sethi, and J. Ullman. Compilers: principles, techniques, and tools. Addison Wesley, 1986.

Digital Library

[3]

}}L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994. (DIKU report 94/19).

[4]

}}Marc Berndl, Ondrej Lhotak, Feng Qian, Laurie Hendren, and Navindra Umanee. Points-to analysis using BDDs. In PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, pages 103--114, New York, NY, USA, 2003. ACM.

Digital Library

[5]

}}Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 35:677--691, 1986.

Digital Library

[6]

}}H. Ehrig and M. Lowe. Parallel and distributed derivations in the single-pushout approach. Theoretical Computer Science, 109:123--143, 1993.

Digital Library

[7]

}}Manuel Fahndrich, Jeffrey S. Foster, Zhendong Su, and Alexander Aiken. Partial online cycle elimination in inclusion constraint graphs. In PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, pages 85--96, New York, NY, USA, 1998. ACM.

Digital Library

[8]

}}Ben Hardekopf and Calvin Lin. The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In PLDI, 2007.

Digital Library

[9]

}}Ben Hardekopf and Calvin Lin. Exploiting pointer and location equivalence to optimize pointer analysis. In SAS, pages 265--280, 2007.

Digital Library

[10]

}}Nevin Heintze and Olivier Tardieu. Ultra-fast aliasing analysis using cla: a million lines of c code in a second. SIGPLAN Not., 36(5):254--263, 2001.

Digital Library

[11]

}}Maurice Herlihy and Eric Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, pages 207--216, New York, NY, USA, 2008. ACM.

Digital Library

[12]

}}Maurice Herlihy and J. Eliot B. Moss. Transactional memory: architectural support for lock-free data structures. In ISCA, 1993.

Digital Library

[13]

}}Michael Hind. Pointer analysis: haven't we solved this problem yet? In PASTE '01: Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, pages 54--61, New York, NY, USA, 2001. ACM.

Digital Library

[14]

}}Vineet Kahlon. 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, pages 249--259, New York, NY, USA, 2008. ACM.

Digital Library

[15]

}}Ken Kennedy and John Allen, editors. Optimizing compilers for modern architectures: a dependence-based approach. Morgan Kaufmann, 2001.

Digital Library

[16]

}}J. W. Klop, Marc Bezem, and R. C. De Vrijer, editors. Term Rewriting Systems. Cambridge University Press, New York, NY, USA, 2001.

Digital Library

[17]

}}Venkata Krishnan and Josep Torrellas. A chip-multiprocessor architecture with speculative multithreading. IEEE Trans. Comput., 48(9):866--880, 1999.

Digital Library

[18]

}}M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic parallelism requires abstractions. SIGPLAN Not. (Proceedings of PLDI 2007), 42(6):211--222, 2007.

Digital Library

[19]

}}Milind Kulkarni, Martin Burtscher, Rajasekhar Inkulu, Keshav Pingali, and Calin Casc¸aval. How much parallelism is there in irregular applications? In Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 3--14, New York, NY, USA, 2009. ACM.

Digital Library

[20]

}}Milind Kulkarni, Keshav Pingali, Ganesh Ramanarayanan, Bruce Walter, Kavita Bala, and L. Paul Chew. Optimistic parallelism benefits from data partitioning. SIGARCH Comput. Archit. News, 36(1):233--243, 2008.

Digital Library

[21]

}}Chris Lattner and Vikram Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO'04), Palo Alto, California, Mar 2004.

Digital Library

[22]

}}Jorn Lind-Nielsen. Buddy, a Binary Decision Diagram package. http://www.itu.dk/research/buddy/. Department of Information Technology, Technical University of Denmark.

[23]

}}Mario Mendez-Lojo, Donald Nguyen, Dimitrios Prountzos, Xin Sui, M. Amber Hassaan, Milind Kulkarni, Martin Burtscher, and Keshav Pingali. Structure-driven optimizations for amorphous data-parallel programs. In Proceedings of the 15th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 3--14, January 2010.

Digital Library

[24]

}}Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Principles of Program Analysis. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1999.

Digital Library

[25]

}}Fernando Magno Quintao Pereira and Daniel Berlin. Wave propagation and deep propagation for pointer analysis. In CGO '09: Proceedings of the 2009 International Symposium on Code Generation and Optimization, pages 126--135,Washington, DC, USA, 2009. IEEE Computer Society.

Digital Library

[26]

}}Keshav Pingali, Milind Kulkarni, Donald Nguyen, Martin Burtscher, Mario Mendez-Lojo, Dimitrios Prountzos, Xin Sui, and Zifei Zhong. Amorphous data parallelism in irregular algorithms. regular tech report TR-09-05, The University of Texas at Austin, 2009.

[27]

}}C. D. Polychronopoulos and D. J. Kuck. Guided selfscheduling: A practical scheduling scheme for parallel supercomputers. IEEE Trans. Comput., 36(12):1425--1439, 1987.

Digital Library

[28]

}}Feng Qian. SableJBDD, a Java Binary Decision Diagram Package. http://www.sable.mcgill.ca/~fqian/ SableJBDD/.

[29]

}}Atanas Rountev and Satish Chandra. Off-line variable substitution for scaling points-to analysis. In PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pages 47--56, New York, NY, USA, 2000. ACM.

Digital Library

[30]

}}Erik Ruf. Partitioning dataflow analyses using types. In POPL '97: Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 15--26, New York, NY, USA, 1997. ACM.

Digital Library

[31]

}}Craig Silverstein. Google Performance Tools. http://code.google.com/p/google-perftools/.

[32]

}}Bjarne Steensgaard. Points-to analysis in almost linear time. In POPL '96: Proceedings of the 23rd ACM SIGPLANSIGACT symposium on Principles of programming languages, pages 32--41, New York, NY, USA, 1996. ACM.

Digital Library

[33]

}}H°akan Sundell and Philippas Tsigas. Lock-free deques and doubly linked lists. J. Parallel Distrib. Comput., 68(7):1008--1020, 2008.

Digital Library

[34]

}}Robert Endre Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22(2):215--225, 1975.

Digital Library

[35]

}}John Whaley and Monica S. Lam. Cloning-based contextsensitive pointer alias analysis using binary decision diagrams. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 131--144, New York, NY, USA, 2004. ACM.

Digital Library

[36]

}}Sean Zhang, Barbara G. Ryder, and William Landi. Program decomposition for pointer aliasing: a step toward practical analyses. SIGSOFT Softw. Eng. Notes, 21(6):81--92, 1996.

Digital Library

Cited By

Szabó TChandra SBlincoe KTonella P(2023)Incrementalizing Production CodeQL AnalysesProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3613860(1716-1726)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3613860
Zuo ZWang KHussain ASani AZhang YLu SDou WWang LLi XWang CXu G(2021)Systemizing Interprocedural Static Analysis of Large-scale Systems Code with GraspanACM Transactions on Computer Systems10.1145/346682038:1-2(1-39)Online publication date: 29-Jul-2021
https://dl.acm.org/doi/10.1145/3466820
Li YLiu BHuang JMussbacher GAtlee JBultan T(2019)SWORDProceedings of the 41st International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion.2019.00042(75-78)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE-Companion.2019.00042
Show More Cited By

Index Terms

Parallel inclusion-based points-to analysis
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Frameworks
      2. Language types
        Parallel programming languages

Recommendations

Parallel inclusion-based points-to analysis
OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

Inclusion-based points-to analysis provides a good trade-off between precision of results and speed of analysis, and it has been incorporated into several production compilers including gcc. There is an extensive literature on how to speed up this ...
A GPU implementation of inclusion-based points-to analysis
PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming

Graphics Processing Units (GPUs) have emerged as powerful accelerators for many regular algorithms that operate on dense arrays and matrices. In contrast, we know relatively little about using GPUs to accelerate highly irregular algorithms that operate ...
A GPU implementation of inclusion-based points-to analysis
PPOPP '12

Graphics Processing Units (GPUs) have emerged as powerful accelerators for many regular algorithms that operate on dense arrays and matrices. In contrast, we know relatively little about using GPUs to accelerate highly irregular algorithms that operate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 45, Issue 10

OOPSLA '10

October 2010

957 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1932682

Issue’s Table of Contents

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications
October 2010
984 pages
ISBN:9781450302036
DOI:10.1145/1869459
General Chairs:
William R. Cook
University of Texas at Austin
,
Siobhán Clarke
Trinity College Dublin
,
Program Chairs:
Martin Rinard
MIT
,
Kevin J. Sullivan
University of Virginia
,
Daniel H. Steinberg
Dim Sum Thinking Inc.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2010

Published in SIGPLAN Volume 45, Issue 10

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
594
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Szabó TChandra SBlincoe KTonella P(2023)Incrementalizing Production CodeQL AnalysesProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3613860(1716-1726)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3613860
Zuo ZWang KHussain ASani AZhang YLu SDou WWang LLi XWang CXu G(2021)Systemizing Interprocedural Static Analysis of Large-scale Systems Code with GraspanACM Transactions on Computer Systems10.1145/346682038:1-2(1-39)Online publication date: 29-Jul-2021
https://dl.acm.org/doi/10.1145/3466820
Li YLiu BHuang JMussbacher GAtlee JBultan T(2019)SWORDProceedings of the 41st International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion.2019.00042(75-78)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE-Companion.2019.00042
Mudduluru RRamanathan M(2014)Efficient Incremental Static Analysis Using Path AbstractionProceedings of the 17th International Conference on Fundamental Approaches to Software Engineering - Volume 841110.1007/978-3-642-54804-8_9(125-139)Online publication date: 5-Apr-2014
https://dl.acm.org/doi/10.1007/978-3-642-54804-8_9
Sato SMorihata A(2014)Syntax-Directed Divide-and-Conquer Data-Flow AnalysisProgramming Languages and Systems10.1007/978-3-319-12736-1_21(392-407)Online publication date: 2014
https://doi.org/10.1007/978-3-319-12736-1_21
Nagaraj VGovindarajan RFensch CO'Boyle MSeznec ABodin F(2013)Parallel flow-sensitive pointer analysis by graph-rewritingProceedings of the 22nd international conference on Parallel architectures and compilation techniques10.5555/2523721.2523728(19-28)Online publication date: 7-Oct-2013
https://dl.acm.org/doi/10.5555/2523721.2523728
Nagaraj VGovindarajan R(2013)Exploring hybrid memory for GPU energy efficiency through software-hardware co-designProceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT.2013.6618800(93-102)Online publication date: Oct-2013
https://doi.org/10.1109/PACT.2013.6618800
Xu RPeng HYang KMao X(2024)Exploring Scalability of Value-Flow Graph ConstructionProceedings of the 2024 4th International Conference on Artificial Intelligence, Automation and High Performance Computing10.1145/3690931.3690951(112-117)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3690931.3690951
Tang WDong DLi SWang CYao PZhou JZhang C(2024) Octopus: Scaling Value-Flow Analysis via Parallel Collection of Realizable Path ConditionsACM Transactions on Software Engineering and Methodology10.1145/363274333:3(1-33)Online publication date: 24-Jan-2024
https://dl.acm.org/doi/10.1145/3632743
Marron MStorm THirschfeld R(2023)Toward Programming Languages for Reasoning: Humans, Symbolic Systems, and AI AgentsProceedings of the 2023 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3622758.3622895(136-152)Online publication date: 18-Oct-2023
https://dl.acm.org/doi/10.1145/3622758.3622895
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