Detecting loop-carried dependences in programs with dynamic data structures

The problem of data dependences detection in codes based on dynamic data structures, is crucial to various compiler optimizations. The approach presented in this paper focuses on detecting data dependences induced by heap-directed pointers on loops that access dynamic data structures. Knowledge abou...

Full description

Saved in:
Bibliographic Details
Published in:Journal of parallel and distributed computing 2007, Vol.67 (1), p.47-62
Main Authors: Navarro, Angeles, Corbera, Francisco, Tineo, Adrian, Asenjo, Rafael, Zapata, Emilio L.
Format: Article
Language:English
Subjects:
Abstract interpretation
Applied sciences
Compiler optimizations
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Data dependence test
Dynamic data structures
Exact sciences and technology
Shape analysis
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of data dependences detection in codes based on dynamic data structures, is crucial to various compiler optimizations. The approach presented in this paper focuses on detecting data dependences induced by heap-directed pointers on loops that access dynamic data structures. Knowledge about the shape of the data structure accessible from a heap-directed pointer provides critical information for disambiguating heap accesses originating from it. The new approach is based on a previously developed shape analysis that maintains topological information of the connections among the different nodes (memory locations) in the data structure. As a novelty, our approach carries out abstract interpretation of the statements being analyzed, annotating memory locations with read/write information. This information will be later used in a very accurate data dependence test which we describe in this paper. We also discuss its application to several different benchmarks.
ISSN:0743-7315
1096-0848
DOI:10.1016/j.jpdc.2006.08.007