Main People Publications Research Tools

Selected publications by date

Selected publications by category

 

Equivalence Analysis: A General Technique To Improve Data-Flow Analyses in the Presence of Pointers

ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering

September 1999, pp. 39-46

Donglin Liang and Mary Jean Harrold

Abstract

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.


Georgia Tech | College of Computing | Software Engineering | Aristotle Home
Updated November 14, 2005 by Jim Jones