Applying DEF/USE Information of Pointer Statements toTraversal-Pattern-Aware Pointer Analysis
Applying DEF/USE Information of Pointer Statements toTraversal-Pattern-Aware Pointer Analysis
Files
Publication or External Link
Date
1998-10-15
Authors
Hwang, Yuan-Shin
Saltz, Joel
Advisor
Citation
DRUM DOI
Abstract
Pointer analysis is essential for optimizing and parallelizing compilers.
It examines pointer assignment statements and estimates pointer-induced
aliases
among pointer variables or possible shapes of dynamic recursive data
structures.
However, previously proposed techniques are not able to gather useful
information or have to give up further optimizations
when overall recursive data structures appear to be cyclic
even though patterns of traversal are linear.
The reason is that these proposed techniques perform pointer analysis
without the knowledge of traversal patterns of
dynamic recursive data structures to be constructed.
This paper proposes an approach, {\em traversal-pattern-aware pointer
analysis},
that has the ability to first identify the structures specified by
traversal patterns of programs from cyclic data structures
and then perform analysis on the specified structures.
This paper presents an algorithm to perform shape analysis on the
structures specified by traversal patterns.
The advantage of this approach is that if the specified structures
are recognized to be acyclic,
parallelization or optimizations can be applied even when
overall data structures might be cyclic.
The DEF/USE information of pointer statements is used
to relate the identified traversal patterns to the pointer statements
which build recursive data structures.
(Also cross-referenced as UMIACS-TR-97-66)