Recovering Logical Data and Code Structures
Michał Cierniak, Wei Li · 1995
Many powerful parallelizing compiler techniques rely on the structures of data and code. Unfortunately, in many real applications, arrays do not have syntactic structures. In this paper, we show that logical data structures can be automatically recovered from the flat, onedimensional arrays and accesses. We present a framework and algorithms for recovering the logical multi-dimensional data structures. This work was supported in part by an NSF Research Initiation Award (CCR-9409120) and ARPA contract F1962894 -C-0057. 1 Introduction Understanding the pattern of array accesses has been identified as a key element of many optimization techniques: it is necessary for achieving good locality of memory references, for deciding data distribution, and for determining data dependences. Many powerful parallelizing compiler techniques are based on the structures of data (e.g. multiple array dimensions) and code (e.g. multiply nested loops). Intuitively, having more information about the log...