Compiling Techniques based on Shape Analysis for Pointer-based Codes in Multiprocessors



Research Goals

Optimizing and parallelizing compilers rely upon accurate static disambiguation of memory references, i.e. determining at compiling time if two given memory references always access disjoint memory locations. Unfortunately thre presence of alias in pointer-based codes makes memory disambiguation a non-trivial issue. An alias arises in a a program when there are two or more disitnc ways to refer to the same memory location. Program constructs that introduce aliases are arrays, pointers and pointer-based dynamic data structures.

Over the past twenty years powerful data dependence analysis have been developed to resolve the problem of array aliases. The problem of calculating pointer-induced aliases, called pointer analysis,  has also received significant attention over the past few years.  Pointer analysis can be divided into two distinct subproblems: stack-directed analysis and heap-directed analysis. We focus our research in the later, which deals with objects dynamically allocated in the heap. An important body of work has been conducted lately on this kind of analysis.  A promising approach to deal with dinamically allocated strucutres consists in explicitly abstracting the dynamic store in the form of a bounded graph.  In other words, the heap is represented as a storage shape graph and the analysis  try to estimate some shape properties of the heap data structures. This type of analysis is called shape analysis. A powerful shape analysis framework has been developed in our research group.

Basically, the goal of our research is to use our shape analysis framework to develop advanced compiling techniques for  parallelism detection and exploiting locality in programs that operate with pointer-based data structures.




Graduate Students:




Last modified -- December 2007,