Article

Free access

Pointer analysis for multithreaded programs

Authors:

Martin RinardAuthors Info & Claims

PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation

Pages 77 - 90

https://doi.org/10.1145/301618.301645

Published: 01 May 1999 Publication History

Abstract

This paper presents a novel interprocedural, flow-sensitive, and context-sensitive pointer analysis algorithm for multithreaded programs that may concurrently update shared pointers. For each pointer and each program point, the algorithm computes a conservative approximation of the memory locations to which that pointer may point. The algorithm correctly handles a full range of constructs in multithreaded programs, including recursive functions, function pointers, structures, arrays, nested structures and arrays, pointer arithmetic, casts between pointer variables of different types, heap and stack allocated memory, shared global variables, and thread-private global variables.We have implemented the algorithm in the SUIF compiler system and used the implementation to analyze a sizable set of multithreaded programs written in the Cilk multithreaded programming language. Our experimental results show that the analysis has good precision and converges quickly for our set of Cilk programs.

References

[1]

Lars Ole Andersen. Program Analysis and Specializa- DIKU, University of Copenhagen, May 1994.

[2]

R. Barua, W. Lee, S. Amarasinghe, and A. Agarwai. Maps: A compiler-managed memory system for Raw m:~r'hlno.~ In Pr,~rporli~gs of the 26th In!er~ati,mal .qyroposture on Computer Architecture, Atlanta, GA, May 1999.

Digital Library

[3]

P. Bogle and B. Liskov. Reducing cross-domain call overhead using batched futures. In Proceedings of the 9th Annual Conference on Object-Oriented Programming Systems, Languages and Applications, Portland, OR, October 1994.

Digital Library

[4]

M. Carlisle and A. Rogers. Software caching and computation migration in Olden. In Proceedings of the 5th A CM SIGPLAN Symposium on Principles and Practice CA, July 1995. ACM, New York.

Digital Library

[5]

G. Cheng, M. Feng, C. Leiserson, K. Randall, and A. Stark. Detecting data races in Cilk programs that use locks. In Proceedings of the lOth Annual A CM Symposium on Parallel Algorithms and Architectures, June 1998.

Digital Library

[6]

J. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointerinduced aliases and side effects. In Conference Record of the Twentieth Annual Symposium on Principles of Programming Languages, Charleston, SC, January 1993. ACM.

Digital Library

[7]

P. Diniz and M. Rinard. Synchronization transformations for parallel computing. In Proceedings of the ~~4th Annual A CM Symposium on the Principles of Programming Languages, pages 187-200, Paris, France, January 1997. ACM, New York.

Digital Library

[8]

M. Emami, R. Ghiya, and L. Hendren. Contextsensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the SIG- PLAN '9~4 Conference on Program Language Design and Implementation, pages 242-256, Orlando, FL, June 1994. ACM, New York.

Digital Library

[9]

B. Falsafi, A. Lebeck, S. Reinhardt, I. Schoinas, M. Hill, J. Larus, A. Rogers, and D. Wood. Application-specific protocols for user-level shared memory. In Proceedings of Supercomputing '9~, pages 380-389, Washington, DC, November 1994. IEEE Computer Society Press, Los Alamitos, Calif.

Digital Library

[10]

M. Frigo, C. Leiserson, and K. Randall. The implementation of the Cilk-5 multithreaded language. In Proceedings of the SIGPLAN '98 Conference on Program Language Design and Implementation, Montreal, Canada, June 1998.

Digital Library

[11]

D. Grunwald and H. Srinivasan. Data flow equations for explicitly parallel programs. In Proceedings of the ~th A CM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, CA, May 1993.

Digital Library

[12]

C. Hauser, C. Jacobi, M. Theimer, B. Welch, and M. Weiser. Using threads in interactive systems: A case study. In Proceedings of the Fourteenth Symposium on Operating Systems Principles, Asheville, NC, December 1993.

Digital Library

[13]

J. Hicks. Experiences with compiler-directed storage reclamation. In Proceedings of the 5th A CM Conference on Functional Programming Languages and Computer Architecture, pages 95-105, June 1993.

Digital Library

[14]

J. Knoop, B. Steffen, and J. Vollmer. Parallelism for free: Efficient and optimal bitvector analyses for parallel programs. A CM 2~ansactions on Programming Languages and Systems, 18(3):268-299, May 1996.

Digital Library

[15]

W. Landi and B. Ryder. A safe approximation algorithm for interprocedural pointer aliasing. In Proceedings of the SIGPLAN '92 Conference on Program Language Design and implementation, San Francisco, CA, June 1992.

Digital Library

[16]

S. Midkiff and D. Padua. Issues in the optimization of parallel programs. In Proceedings of the 1990 International Conference on Parallel Processing, pages II-105- 113, 1990.

[17]

R. O'Callahan and D. Jackson. Lackwit: A program understanding tool based on type inference: In 1997 International Conference on Software Engineering, Boston, MA, May 1997.

Digital Library

[18]

J. Reppy. Higher-order Concurrency. PhD thesis, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y., June 1992.

Digital Library

[19]

E. Ruf. Context-insensitive alias analysis reconsidered. In Proceedings of the SIGPLAN '95 Conference on Program Language Design and Implementation, La Jolla, CA, June 1995.

Digital Library

[20]

R. Rugina and M. Rinard. Automatic parallelization of divide and conquer algorithms. In Proceedings of the 7th A CM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Atlanta, GA, May 1999.

Digital Library

[21]

S. Savage, M. Burrows, G. Nelson, P. Solbovarro, and T. Anderson. Eraser: A dynamic race detector for multi-threaded programs. In Proceedings of the Sixteenth Symposium on Operating Systems Principles, Saint-Malo, France, October 1997.

Digital Library

[22]

M. Shapiro and S. Horwitz. Fast and accurate flowinsensitive points-to analysis. In Proceedings of the 2Jth Annual A CM Symposium on the Principles of Programming Languages, Paris, France, January 1997.

Digital Library

[23]

Bjarne Steensgaard. Points-to analysis in almost linear time. In Proceedings of the ~3rd Annual A CM Symposium on the Principles of Programming Languages, St. Petersburg Beach, FL, January 1996.

Digital Library

[24]

P. Stocks, B. Ryder, W. Landi, and S. Zhang. Comparing flow and context sensitivity on the modification side-effects problem. In 1998 International Symposium on Software Testing and Analysis, Clearwater, FL, March 1998.

Digital Library

[25]

R. Wilson and M. Lain. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the SIGPLAN '95 Conference on Program Language Design and Implementation, La Jolla, CA, June 1995. ACM, New York.

Digital Library

[26]

H. Zhu and L. Hendren. Communication optimizations for parallel C programs. In Proceedings of the SIG- PLAN '98 Conference on Program Language Design and Implementation, Montreal, Canada, June 1998.

Digital Library

Cited By

Zhu SGuo YZhang LCai YGrundy JPollock LPenta M(2023)Tolerate Control-Flow Changes for Sound Data Race PredictionProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00118(1342-1354)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00118
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
Helland P(2018)Consistently EventualQueue10.1145/3212477.322607716:2(5-12)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1145/3212477.3226077
Show More Cited By

Index Terms

Pointer analysis for multithreaded programs
1. General and reference
  1. Document types
    1. Computing standards, RFCs and guidelines
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Multithreading

Recommendations

Sparse flow-sensitive pointer analysis for multithreaded programs
CGO '16: Proceedings of the 2016 International Symposium on Code Generation and Optimization

For C programs, flow-sensitivity is important to enable pointer analysis to achieve highly usable precision. Despite significant recent advances in scaling flow-sensitive pointer analysis sparsely for sequential C programs, relatively little progress ...
Pointer analysis for multithreaded programs

This paper presents a novel interprocedural, flow-sensitive, and context-sensitive pointer analysis algorithm for multithreaded programs that may concurrently update shared pointers. For each pointer and each program point, the algorithm computes a ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation

May 1999

304 pages

ISBN:1581130945

DOI:10.1145/301618

Chairmen:
Barbara G. Ryder
Rutgers Univ., New Brunswick, NJ
,
Benjamin G. Zorn
Univ. of Colorado, Boulder, and Microsoft Research

ACM SIGPLAN Notices Volume 34, Issue 5
May 1999
304 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/301631
Editors:
Barbara G. Ryder
Rutgers Univ., New Brunswick, NJ
,
Benjamin G. Zorn
Univ. of Colorado, Boulder
,
A. Michael Berman
Rowan Univ., Glassboro, NJ
Issue’s Table of Contents

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI99

Sponsor:

PLDI99: Conference on Programming Language Design and Implementation 1999

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

PLDI '99 Paper Acceptance Rate 26 of 130 submissions, 20%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

131
Total Citations
View Citations
1,105
Total Downloads

Downloads (Last 12 months)143
Downloads (Last 6 weeks)13

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu SGuo YZhang LCai YGrundy JPollock LPenta M(2023)Tolerate Control-Flow Changes for Sound Data Race PredictionProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00118(1342-1354)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00118
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
Helland P(2018)Consistently EventualQueue10.1145/3212477.322607716:2(5-12)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1145/3212477.3226077
Petrov A(2018)Algorithms Behind Modern Storage SystemsQueue10.1145/3212477.322026616:2(31-51)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1145/3212477.3220266
Chisnall D(2018)C Is Not a Low-level LanguageQueue10.1145/3212477.321247916:2(18-30)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1145/3212477.3212479
Kjolstad FKamil SChou SLugato DAmarasinghe S(2017)The tensor algebra compilerProceedings of the ACM on Programming Languages10.1145/31339011:OOPSLA(1-29)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133901
Scott RNavarro Leija ODevietti JNewton R(2017)Monadic composition for deterministic, parallel batch processingProceedings of the ACM on Programming Languages10.1145/31338971:OOPSLA(1-26)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133897
Colazzo DGhelli GSartiani C(2017)Linear Time Membership in a Class of Regular Expressions with Counting, Interleaving, and Unordered ConcatenationACM Transactions on Database Systems10.1145/313270142:4(1-44)Online publication date: 13-Nov-2017
https://dl.acm.org/doi/10.1145/3132701
BáRány VCate BKimelfeld BOlteanu DVagena Z(2017)Declarative Probabilistic Programming with DatalogACM Transactions on Database Systems10.1145/313270042:4(1-35)Online publication date: 27-Oct-2017
https://dl.acm.org/doi/10.1145/3132700
Ripamonti LTrubian MMaggiorini DPreviti S(2017)Video Games and Operations ResearchComputers in Entertainment 10.1145/276713616:1(1-12)Online publication date: 23-Dec-2017
https://dl.acm.org/doi/10.1145/2767136
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents