Title :
A novel approach for detecting heap-based loop-carried dependences
Author :
Tineo, A. ; Corbera, F. ; Navarro, A. ; Asenjo, R. ; Zapata, E.L.
Author_Institution :
Dept. of Comput. Archit., Malaga Univ., Spain
Abstract :
The problem of data dependences in pointer-based codes is crucial to various compiler optimizations. The approach presented in this paper focus 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. Our 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 dependence test, which we describe in this paper. We also discuss its application to three different programs: the sparse matrix-vector product, mst from Olden and twolf from the SPEC CPU2000 suite.
Keywords :
data structures; optimising compilers; program control structures; storage management; abstract interpretation; compiler optimizations; data dependence detection; dynamic data structures; heap-directed pointers; memory locations; shape analysis; sparse matrix-vector product; Computer architecture; Data structures; Information analysis; Optimizing compilers; Program processors; Read-write memory; Shape; Sparse matrices; Testing; Tree data structures;
Conference_Titel :
Parallel Processing, 2005. ICPP 2005. International Conference on
Print_ISBN :
0-7695-2380-3
DOI :
10.1109/ICPP.2005.11