language: en

[To appear in Proceedings of the Twenty Third ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St. Petersburg Beach, Florida, January 21-24, 1996. c fl1996 ACM (see notice below).]

Is it a Tree, a DAG, or a Cyclic Graph? A Shape Analysis for Heap-Directed Pointers in C

Rakesh Ghiya and Laurie J. Hendren
School of Computer Science, McGill University
Montreal, Quebec, CANADA H3A 2A7
{ghiya,hendren}@cs.mcgill.ca

Abstract This paper reports on the design and implementation of a practical shape analysis for C. The purpose of the analysis is to aid in the disambiguation of heap-allocated data structures by estimating the shape (Tree, DAG, or Cyclic Graph) of the data structure accessible from each heap-directed pointer. This shape information can be used to improve dependence testing and in parallelization, and to guide the choice of more complex heap analyses. The method has been implemented as a context-sensitive interprocedural analysis in the McCAT compiler. Experimental results and observations are given for 16 benchmark programs. These results show that the analysis gives accurate and useful results for an important group of applications.

1 Introduction and Related