Master's thesis on heap analysis available.

My Master's thesis on analyzing the alias properties of heap-based
dynamic data structures, entitled "Practical Techniques for
Interprocedural Heap Analysis", is now available via anon ftp from
wally.cs.mcgill.ca:/pub/doc/thesis/ghiya/thesis.ps.gz. It extends
the previous work done at McGill on alias analysis for stack-based
structures (by Maryam Emami).


Rakesh Ghiya.
School of CS
McGill Univ
Montreal, Canada.


---------------------------Abstract--------------------------------------


Accurate alias analysis is critical for optimizing/parallelizing
compilers that support languages with pointers. Efficient techniques
have been developed to calculate aliases introduced by pointers to
named memory locations (typically on the stack). However, practical
and effective techniques for detection
of aliases induced by heap-based dynamic data structures, have yet
to be developed. Existing approaches are either efficient but
overly conservative, or sophisticated but expensive.


In this thesis, we present a new and practical approach for analyzing
the alias properties of heap data structures. The important features
of our approach include: (i) we analyze heap-directed pointers after
resolving the points-to relationships of stack-directed pointers,
(ii) we use a
{\em storeless} model and estimate the heap structure by abstracting
the relationships between heap-directed pointers, and
not by explicitly abstracting the heap as a graph, and (iii) we employ a
hierarchical approach and design different abstractions to
solve the problem at different levels of complexity.


We present a hierarchy of three practical abstractions for analyzing
heap data structures, namely connection, direction and interference
matrix abstractions. These abstractions respectively capture the
following {\em boolean}
relationships between any two given heap-directed pointers: (i) if they
can point to the same heap data structure, (ii) if an access path exists
between the heap objects they point to, and (iii) if they can
access a common heap object. Connection matrix information helps
detect pointer accesses to completely disjoint data structures.
The other two abstractions work together to identify if the
given program builds tree-like or dag-like structures.


We have implemented context-sensitive interprocedural analyses
for these abstractions in the framework of the McCAT C compiler.
For each abstraction, we first present basic analysis rules applicable
to any language that supports pointers. We then describe C specific
features of the analyses. We demonstrate the effectiveness of the
analyses by providing examples as well as empirical results for
real C programs.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.