## Efficient Points-To Analysis for Whole-Program Analysis

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

Related research categories: |
---|

| (1) Program Analysis |

| (2) Empirical Studies |

| (3) Data Flow |

| (4) Pointer Analysis |

| (5) Slicing |