Online Cycle Detection and Difference Propagation for Pointer Analysis

Author(s). David J. Pearce, Paul H.J. Kelly and Chris Hankin.

Venue. In Workshop on Source Code Analysis and Manipulation (SCAM), pages 3--12, 2003. ©IEEE

Abstract. This paper presents and evaluates a number of techniques to improve the execution time of interprocedural pointer analysis in the context of large C programs. The analysis is formulated as a graph of set constraints and solved using a worklist algorithm. Indirections lead to new constraints being added during this process. In this work, we present a new algorithm for online cycle detection, and a difference propagation technique which records changes in a variable’s solution. Effectiveness of these and other methods are evaluated experimentally using nine common ‘C’ programs ranging between 1000 to 55000 lines of code.