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

Peng Wu, Paul Feautrier, David Padua, Zehra Sura

Research output: Contribution to conferencePaper

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.

Original languageEnglish (US)
Pages262-273
Number of pages12
StatePublished - Jan 1 2002
Externally publishedYes
EventConference Proceedings of the 2002 International Conference on Supercomputing - New York, NY, United States
Duration: Jun 22 2002Jun 26 2002

Other

OtherConference Proceedings of the 2002 International Conference on Supercomputing
CountryUnited States
CityNew York, NY
Period6/22/026/26/02

Fingerprint

Testing

Keywords

  • Dependence analysis
  • Heap analysis
  • Java
  • Pointer analysis
  • Pointer arrays

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Wu, P., Feautrier, P., Padua, D., & Sura, Z. (2002). Instance-wise points-to analysis for loop-based dependence testing. 262-273. Paper presented at Conference Proceedings of the 2002 International Conference on Supercomputing, New York, NY, United States.

Instance-wise points-to analysis for loop-based dependence testing. / Wu, Peng; Feautrier, Paul; Padua, David; Sura, Zehra.

2002. 262-273 Paper presented at Conference Proceedings of the 2002 International Conference on Supercomputing, New York, NY, United States.

Research output: Contribution to conferencePaper

Wu, P, Feautrier, P, Padua, D & Sura, Z 2002, 'Instance-wise points-to analysis for loop-based dependence testing', Paper presented at Conference Proceedings of the 2002 International Conference on Supercomputing, New York, NY, United States, 6/22/02 - 6/26/02 pp. 262-273.
Wu P, Feautrier P, Padua D, Sura Z. Instance-wise points-to analysis for loop-based dependence testing. 2002. Paper presented at Conference Proceedings of the 2002 International Conference on Supercomputing, New York, NY, United States.
Wu, Peng ; Feautrier, Paul ; Padua, David ; Sura, Zehra. / Instance-wise points-to analysis for loop-based dependence testing. Paper presented at Conference Proceedings of the 2002 International Conference on Supercomputing, New York, NY, United States.12 p.
@conference{fe97cba389774fc6936d7263aab6f399,
title = "Instance-wise points-to analysis for loop-based dependence testing",
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.",
keywords = "Dependence analysis, Heap analysis, Java, Pointer analysis, Pointer arrays",
author = "Peng Wu and Paul Feautrier and David Padua and Zehra Sura",
year = "2002",
month = "1",
day = "1",
language = "English (US)",
pages = "262--273",
note = "Conference Proceedings of the 2002 International Conference on Supercomputing ; Conference date: 22-06-2002 Through 26-06-2002",

}

TY - CONF

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

AU - Wu, Peng

AU - Feautrier, Paul

AU - Padua, David

AU - Sura, Zehra

PY - 2002/1/1

Y1 - 2002/1/1

N2 - 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.

AB - 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.

KW - Dependence analysis

KW - Heap analysis

KW - Java

KW - Pointer analysis

KW - Pointer arrays

UR - http://www.scopus.com/inward/record.url?scp=0036374226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036374226&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0036374226

SP - 262

EP - 273

ER -