Home |
People |
Research |
Awards/Honours |
Publications |
Lab Resources |
Gallery |
Contact Info |
Sponsored Research
MSc(Engg) Thesis, Supercomputer Education and Research Centre,
Indian Institute of Science, Bangalore, India, August 2014.
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 anal- ysis 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 analy- sis. 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 prob- lem 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 algo- rithm using Intel Threading Building Blocks and demonstrate considerable scaling (upto 4.05x) for 8 threads on a set of 10 benchmarks. Compared to the sequential implementa- tion 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 speedup the computa- tion 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 preci- sion 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.