Progressive Shape Analysis for Real C Codes
F. Corbera - R. Asenjo - E. Zapata
Computer Architecture Department. University of Málaga. Spain.
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.
Rafael Asenjo Plaza