Equivalence Analysis: A General Technique To Improve Data-Flow
Analyses in the Presence of Pointers
Workshop on Program Analysis for Software Tools and Engineering
September 1999, pp. 39-46
Donglin Liang and Mary Jean Harrold
Existing methods to handle pointer variables during data-flow analyses can
make such analyses inefficient both in time and space because
the data-flow analyses must store and propagate large sets of data facts
that are introduced by dereferences of pointer variable.
This paper presents equivalence analysis, a general technique to improve the
efficiency of data-flow analyses in the presence of pointers.
The technique identifies equivalence
relations among the memory locations accessed by a procedure and
ensures that two equivalent memory locations share the
same set of data facts in a procedure and in the procedures
that are called by that procedure.
Thus, a data-flow analysis needs to compute the data-flow information only
for a representative memory location in an equivalence class.
The data-flow information for other memory locations in the equivalence class
can be derived from that of the representative memory location.
Our empirical studies indicate that equivalence analysis may effectively improve
the efficiency of many data-flow analyses.