Compile-Time Analysis on Programs with Dynamic Pointer-Linked Data
Structures
Compile-Time Analysis on Programs with Dynamic Pointer-Linked Data
Structures
Files
Publication or External Link
Date
1998-10-15
Authors
Hwang, Yuan-Shin
Saltz, Joel
Advisor
Citation
DRUM DOI
Abstract
This paper studies static analysis on programs
that create and traverse dynamic pointer-linked data structures.
It introduces a new type of auxiliary structures, called {\em link graphs},
to depict the alias information of pointers and connection relationships
of dynamic pointer-linked data structures.
The link graphs can be used by compilers to detect side effects,
to identify the patterns of traversal, and to gather the
DEF-USE information of dynamic pointer-linked data structures.
The results of the above compile-time analysis are essential
for parallelization and optimizations on communication and
synchronization overheads.
Algorithms that perform compile-time analysis on side effects
and DEF-USE information using link graphs will be proposed.