Shape Analysis

F. Corbera - R. Asenjo - E.L. Zapata

Computer Architecture Department. University of Malaga.
e-mail: {corbera,asenjo,ezapata}


To successfully exploit all the possibilities of current computer/multicomputer architectures, optimization compiling techniques are a must. However, for codes based on pointers and dynamic data structures these optimization techniques have to be necessarily carried out after identifying the characteristics and properties of the data structure used in the code. In this work we present the first method able to automatically identify complex dynamic data structures used in a code even in the presence of arrays of pointers. This method has been implemented in a compiler which symbolically executes the input code to generate a set of graphs, called RSRSG (Reduced Set of Reference Shape Graphs), for each sentence. Each RSRSG accurately describes the data structure configuration at each program point. In order to deal with arrays of pointers we have introduced two main concepts: the multireference class, and instances. The compiler has been validated with several codes based on complex data structures containing arrays of pointers which were successfully identified.

Rafael Asenjo Plaza
Last modified: Tue Mar 7 13:49:11 CET 2006