Parallel flow-sensitive pointer analysis by graph-rewriting

Proceedings of the 22nd international conference on Parallel architectures and compilation techniques
Edinburgh, Scotland, September 7--11, 2013

Authors

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

Abstract

Precise pointer analysis is a problem of interest to both the compiler and the program verification community. Flow- sensitivity is an important dimension of pointer analysis that affects the precision of the final result computed. Scaling flow-sensitive pointer analysis to millions of lines of code is a major challenge.Recently, staged flow-sensitive pointer analysis has been pro-posed, which exploits a sparse representation of program code created by staged analysis. In this paper we formulate the staged flow-sensitive pointer analysis as a graph-rewriting problem.Graph-rewriting has already been used for flow-insensitive anal- ysis. However, formulating flow-sensitive pointer analysis as a graph-rewriting problem adds additional challenges due to the nature of flow-sensitivity. We implement our parallel algorithm using Intel Threading Building Blocks and demonstrate considerable scaling (upto 2.6x) 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 8 of the benchmarks.

Download

Full Text