Approximating flow-sensitive pointer analysis using frequent itemset mining

Abstract

Pointer alias analysis is a well researched problem in the area of compilers and program verification. Many recent works in this area have focused on flow-sensitivity due to the additional precision it offers. However, a flow-sensitive analysis is computationally expensive, thus, preventing its use in larger programs. In this work, we observe that a number of object sets, consisting of tens to hundreds of objects appear together and frequently in many points-to sets. By approximating each of these object sets by a single object, we can speedup computation of points-to sets. Although the proposed approach incurs a slight loss in precision, it is shown to be safe. We use a well known data mining technique called frequent itemset mining to find these frequently occurring objects. We compare our approximation to a fully flow-sensitive pointer analysis on a set of ten benchmarks. We measure precision loss using two common client analysis queries and report an average precision loss of 0.25% on one measure and 1.40% on the other. The proposed approach results in a speedup of upto 12.9× (and an average speedup of 6.2×) in computing the points-to sets.