next up previous
Next: Motivation

Progressive Shape Analysis for Real C Codes 1

F. Corbera - R. Asenjo - E. Zapata
  
- Computer Architecture Department. University of Málaga. Spain.
e-mail: {corbera,asenjo,ezapata}@ac.uma.es

Abstract:

Dynamic and pointer-based data structures are widely used in symbolic or irregular C codes. However, there is still a lack of compiler techniques to deal with the automatic optimization of such codes. In this paper we take a first step towards this final objective: the automatic identification of the data structure used in the code. More precisely, we describe the framework and the compiler we have implemented to capture complex data structures generated, traversed, and modified in C codes. Our method assigns a Reduced Set of Reference Shape Graphs (RSRSG) to each sentence to approximate the shape of the data structure after the execution of such a sentence. With the properties and operations that define the behavior of our RSRSG, the method can accurately detect complex recursive data structures such as a doubly linked list of pointers to trees where the leaves point to additional lists. For more complex structures like the octree of the Barnes-Hut N-body algorithm, the compiler resorts to a progressive analysis in which the level of detail is increased during the analysis when needed. Other experiments are also carried out with sparse codes to validate the capabilities of our compiler.

Keywords: Shape Analysis, Pointers, Recursive Data Structures, Shape Graphs, C codes.

Technical areas: Compilers and Languages, Optimizing Compilers.




next up previous
Next: Motivation
Rafael Asenjo Plaza 2002-02-19