|
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.
|