Online Cycle Detection and Difference Propagation: Applications to Pointer Analysis

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

Venue. In Software Quality Journal, 12 (4), pages 209--335, 2004. ©Kluwer Academic Publishers

Abstract. This paper presents and evaluates a number of techniques to improve the execution time of interprocedural pointer analysis in the context of C programs. The analysis is formulated as a graph of set constraintsand solved using a worklist algorithm. Indirections lead to new constraints being added during this procedure.The solution process can be simplified by identifying cycles, and we present a novel online algorithm for doingthis. We also present a difference propagation scheme which avoids redundant work by tracking changes to eachsolution set. The effectiveness of these and other methods are shown in an experimental study over 12 common‘C’ programs ranging between 1000 to 150,000 lines of code.