Main People Publications Research Tools

Selected publications by date

Selected publications by category

 

Efficient Points-To Analysis for Whole-Program Analysis

Proceedings of the 7th European Software Engineering Conference and 7th ACM SIGSOFT Symposium on the Foundations of Software Engineering

September 1999

Donglin Liang and Mary Jean Harrold

Abstract

To function on programs written in languages such as C that make extensive use of pointers, automated software engineering tools require safe alias information. Existing alias-analysis techniques that are sufficiently efficient for analysis on large software systems may provide alias information that is too imprecise for tools that use it: the imprecision of the alias information may (1) reduce the precision of the information provided by the tools and (2) increase the cost of the tools. This paper presents a flow-insensitive, context-sensitive points-to analysis algorithm that computes alias information that is almost as precise as that computed by Andersen's algorithm -- the most precise flow- and context-insensitive algorithm -- and almost as efficient as Steensgaard's algorithm -- the most efficient flow- and context-insensitive algorithm. Our empirical studies show that our algorithm scales to large programs better than Andersen's algorithm and show that flow-insensitive alias analysis algorithms, such as our algorithm and Andersen's algorithm, can compute alias information that is close in precision to that computed by the more expensive flow- and context-sensitive alias analysis algorithms.


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