Online cycle detection and difference propagation for pointer analysis

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.