Approximating flow-sensitive pointer analysis using frequent itemset mining

Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2015
San Francisco, CA, USA, February 07--11, 2015

Authors

1. Vaivaswatha Nagaraj, Supercomputer Education and Research Centre
2. R. Govindarajan, Supercomputer Education and Research Centre; Department of Computer Science and Automation

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.9x (and an average speedup of 6.2x) in computing the points-to sets.

Download

Full Text