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
DOIs
StatePublished - 2002
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

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Instance-wise points-to analysis for loop-based dependence testing'. Together they form a unique fingerprint.

  • 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. https://doi.org/10.1145/514225.514228