Article

Instance-wise points-to analysis for loop-based dependence testing

Authors:

Paul Feautrier,

Zehra SuraAuthors Info & Claims

ICS '02: Proceedings of the 16th international conference on Supercomputing

Pages 262 - 273

https://doi.org/10.1145/514191.514228

Published: 22 June 2002 Publication History

Abstract

We present a points-to analysis that aims at enabling loop-based dependence analysis in the presence of Java references. The analysis is based on an abstraction called element-wise points-to (ewpt) mapping. An ewpt mapping summarizes, in a compact representation, the relation between a pointer and the heap object it points to, for every instance of the pointer inside a loop and for every array element directly accessible through this pointer. Such instance-wise and element-wise information is especially important for loop-based dependence analyses and for a language where multi-dimensional arrays are implemented as arrays of pointers. We describe an iterative algorithm to compute ewpt mappings. We also present techniques to remove objects from ewpt mappings for destructive updates.The points-to algorithm was implemented and evaluated on a set of benchmark programs. We demonstrate that ewpt information can significantly improve the precision of dependence analysis. In many cases, the dependence analysis reports no false dependences due to array accesses.

References

[1]

Rastislav Bodik, Ragiv Gupta, and Vivek Sarkar. ABCD: Eliminating array bounds checks on demand. In ACM Symp. on Programming Language Design and Implementation, June 2000]]

Digital Library

[2]

C. Chambers, I. Pechtchanski, V. Sarkar, M. Serrano, and H. Srinivasan. Dependence analysis for Java. In Workshop on Languages and Compilers for Parallel Computing, August 1999]]

Digital Library

[3]

Ben-Chung Cheng and Wen mei Hwu. Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation. In ACM Symp. on Programming Language Design and Implementation, pages 57--69, June 2000]]

Digital Library

[4]

Jong-Deok Choi, Michael Burke, and Paul Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In ACM Symp. on Principles of Programming Languages, pages 232--245, 1993]]

Digital Library

[5]

Albert Cohen, Peng Wu, and David Padua. Pointer analysis for monotonic container traversals. Technical Report CSRD 1586, University of Illinois at Urbana-Champaign, January 2001]]

[6]

Alain Deutsch. Interprocedural may-alias analysis for pointers: Beyond k-limiting. In ACM Symp. on Programming Language Design and Implementation, June 1994]]

Digital Library

[7]

A. Diwan, K.S. McKinley, and E.B. Moss. Type-based alias analysis. In ACM Symp. on Programming Language Design and Implementation, June 1998]]

Digital Library

[8]

Rakesh Ghiya and Laurie J. Hendren. Connection analysis: A practical interprocedural heap analysis for C. In Workshop on Languages and Compilers for Parallel Computing. Springer-Verlag, 1995]]

Digital Library

[9]

Rakesh Ghiya and Laurie J. Hendren. Putting pointer analysis to work. In ACM Symp. on Principles of Programming Languages, January 1998]]

Digital Library

[10]

Laurie J. Hendren and Alexandru Nicolau. Parallelizing programs with recursive data structures. In IEEE Trans. on Parallel and Distributed Computing, January 1990]]

Digital Library

[11]

Joseph Hummel, Laurie~J. Hendren, and Alex Nicolau. A general data dependence test for dynamic, pointer-based data structures. In ACM Symp. on Programming Language Design and Implementation, June 1994]]

Digital Library

[12]

Joseph Hummel, Laurie~J. Hendren, and Alex Nicolau. A language for conveying the alising properties of dynamic, pointer-based data structures. In Inthernational Parallel Processing Symposium, pages 208--216, April 1994]]

Digital Library

[13]

J. Larus and P. Hilfinger. Detecting conflicts between structure accesses. In ACM Symp. on Programming Language Design and Implementation, Atlanta, GA, June 1988]]

Digital Library

[14]

J. E. Moreira, S. P. Midkiff, and M. Gupta. From flop to megaflops: Java for technical computing. ACM Trans. on Programming Languages and Systems, 22(2):265--295, March 2000]]

Digital Library

[15]

William Pugh. The Omega test: A fast and practical integer programming algorithm for dependence analysis. In Supercomputing, 1991]]

Digital Library

[16]

Radu Rugina and Martin Rinart. Symbolic bound analysis of pointers, array indices and accessed memory regions. In PLDI'2000. ACM, 2000]]

Digital Library

[17]

M. Sagiv, T. Reps, and R. Wilhelm. Solving shape analysis problems in languages with destructive updating. In ACM Symp. on Principles of Programming Languages, January 1996]]

Digital Library

[18]

B. Steensgaard. Points-to analysis in almost linear time. In ACM Symp. on Principles of Programming Languages, January 1996]]

Digital Library

[19]

R. Wilson and M. Lam. Efficient context-sensitive pointer analysis for C programs. In ACM Symp. on Programming Language Design and Implementation, June 1995]]

Digital Library

[20]

Peng Wu. Analyses of pointers, induction variables, and container objects for dependence testing. Technical Report UIUCDCS-R-2001-2209, University of Illinois at Urbana-Champaign, May 2001. Ph.D Thesis]]

Digital Library

Cited By

Dean JMitropoulos FCho YShin SKim SHung CHong J(2014)An aspect pointcut for parallelizable loopsProceedings of the 29th Annual ACM Symposium on Applied Computing10.1145/2554850.2554917(1619-1624)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.1145/2554850.2554917
Yuki TFeautrier PRajopadhye SSaraswat V(2013)Array dataflow analysis for polyhedral X10 programsACM SIGPLAN Notices10.1145/2517327.244252048:8(23-34)Online publication date: 23-Feb-2013
https://dl.acm.org/doi/10.1145/2517327.2442520
Yuki TFeautrier PRajopadhye SSaraswat VNicolau AShen XAmarasinghe SVuduc R(2013)Array dataflow analysis for polyhedral X10 programsProceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/2442516.2442520(23-34)Online publication date: 23-Feb-2013
https://dl.acm.org/doi/10.1145/2442516.2442520
Show More Cited By

Index Terms

Instance-wise points-to analysis for loop-based dependence testing
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Connection Analysis: A Practical Interprocedural Heap Analysis for C
Special issue: selected papers from the eighth international workshop on languages and compilers for parallel computing

This paper presents a practical heap analysis technique, connection analysis, that can be used to disambiguate heap accesses in C programs. The technique is designed for analyzing programs that allocate many disjoint objects in the heap such as ...
A probabilistic pointer analysis for speculative optimizations
Proceedings of the 2006 ASPLOS Conference

Pointer analysis is a critical compiler analysis used to disambiguate the indirect memory references that result from the use of pointers and pointer-based data structures. A conventional pointer analysis deduces for every pair of pointers, at any ...
A probabilistic pointer analysis for speculative optimizations
Proceedings of the 2006 ASPLOS Conference

Pointer analysis is a critical compiler analysis used to disambiguate the indirect memory references that result from the use of pointers and pointer-based data structures. A conventional pointer analysis deduces for every pair of pointers, at any ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '02: Proceedings of the 16th international conference on Supercomputing

June 2002

338 pages

ISBN:1581134835

DOI:10.1145/514191

General Chair:
Kemal Ebcioglu
IBM T.J. Watson Research Center
,
Program Chairs:
Keshav Pingali
Cornell University
,
Alex Nicolau
University of California

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

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICS02

Sponsor:

SIGARCH

ICS02: International Conference on Supercomputing

June 22 - 26, 2002

New York, New York, USA

Acceptance Rates

ICS '02 Paper Acceptance Rate 31 of 144 submissions, 22%;

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
383
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dean JMitropoulos FCho YShin SKim SHung CHong J(2014)An aspect pointcut for parallelizable loopsProceedings of the 29th Annual ACM Symposium on Applied Computing10.1145/2554850.2554917(1619-1624)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.1145/2554850.2554917
Yuki TFeautrier PRajopadhye SSaraswat V(2013)Array dataflow analysis for polyhedral X10 programsACM SIGPLAN Notices10.1145/2517327.244252048:8(23-34)Online publication date: 23-Feb-2013
https://dl.acm.org/doi/10.1145/2517327.2442520
Yuki TFeautrier PRajopadhye SSaraswat VNicolau AShen XAmarasinghe SVuduc R(2013)Array dataflow analysis for polyhedral X10 programsProceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/2442516.2442520(23-34)Online publication date: 23-Feb-2013
https://dl.acm.org/doi/10.1145/2442516.2442520
Wimmer CMössenböck HSoffa MDuesterwald E(2008)Automatic array inlining in java virtual machinesProceedings of the 6th annual IEEE/ACM international symposium on Code generation and optimization10.1145/1356058.1356061(14-23)Online publication date: 6-Apr-2008
https://dl.acm.org/doi/10.1145/1356058.1356061
Ryoo SRodrigues CHwu W(2007)Iteration Disambiguation for Parallelism Identification in Time-Sliced ApplicationsLanguages and Compilers for Parallel Computing10.1007/978-3-540-85261-2_8(110-124)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1007/978-3-540-85261-2_8
Chen PHung MHwang YJu RLee J(2003)Compiler support for speculative multithreading architecture with probabilistic points-to analysisACM SIGPLAN Notices10.1145/966049.78150238:10(25-36)Online publication date: 11-Jun-2003
https://dl.acm.org/doi/10.1145/966049.781502
Chen PHung MHwang YJu RLee JEigenmann RRinard M(2003)Compiler support for speculative multithreading architecture with probabilistic points-to analysisProceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/781498.781502(25-36)Online publication date: 11-Jun-2003
https://dl.acm.org/doi/10.1145/781498.781502

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