| dc.description.abstract | Pointer alias analysis is a well-researched problem in the area of compilers and static program analysis. Many recent works in this area have focused on flow-sensitivity due to the additional precision it offers. Precise analyses allow clients to make more accurate and useful decisions. With higher precision, a compiler can perform more optimizations and a static analysis tool can report more useful information about a program.
Flow-sensitivity is a dimension of pointer analysis that determines whether the analysis takes the program’s control flow into account. A flow-sensitive pointer analysis computes points-to sets for pointers at each program point, and hence, is more precise than a flow-insensitive analysis. However, a flow-sensitive analysis is computationally expensive. This has limited its use in larger programs. Earlier works on flow-sensitive pointer analysis have dealt with scaling it to larger programs. In this work, we propose and study two approaches to further decrease the time taken by a flow-sensitive analysis.
We propose a technique to parallelize flow-sensitive pointer analysis, thus allowing it to utilize multiple processor cores. We also introduce an approximation algorithm for flow-sensitive pointer analysis, enabling faster execution with a small precision loss.
In the first part of our work, we formulate the staged flow-sensitive pointer analysis as a graph-rewriting problem. Graph-rewriting has already been used for flow-insensitive analysis. However, formulating flow-sensitive pointer analysis as a graph-rewriting problem adds additional challenges due to the nature of flow-sensitivity. In particular, we identify two key challenges that flow-sensitivity adds to a graph-rewriting formulation of pointer analysis and provide solutions to handle them. We implement our parallel algorithm using Intel Threading Building Blocks and demonstrate considerable scaling (up to 4.05x) for 8 threads on a set of 10 benchmarks. Compared to the sequential implementation of staged flow-sensitive analysis, a single-threaded execution of our implementation performs better in 9 out of the 10 benchmarks.
In the second part of our 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. We observe that propagating these large points-to sets during the analysis is expensive. By approximating each of these object sets by a single object, we can speed up the 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 object sets. We compare our approximation to a fully flow-sensitive pointer analysis on a set of 10 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 up to 12.9x (and an average speedup of 6.2x) in computing the points-to sets. | |
