Paper Info
Title
Parallel Sparse Flow-Sensitive Points-To Analysis
Abstract
This paper aims to contribute to further advances in pointer (or points-to) analysis algorithms along the combined dimensions of precision, scalability, and performance. For precision, we aim to support interprocedural flow-sensitive analysis. For scalability, we aim to show that our approach scales to large applications with reasonable memory requirements. For performance, we aim to design a points-to analysis algorithm that is amenable to parallel execution. The algorithm introduced in this paper achieves all these goals. As an example, our experimental results show that our algorithm can analyze the 2.2MLOC Tizen OS framework with < 16GB of memory while delivering an average analysis rate of > 10KLOC/second.Our points-to analysis algorithm, PSEGPT, is based on the Pointer Sparse Evaluation Graph (PSEG) form, a new analysis representation that combines both points-to and heap def-use information. PSEGPT is a scalable interprocedural flow-sensitive context-insensitive points-to analysis that is amenable to efficient task-parallel implementations, even though points-to analysis is usually viewed as a challenge problem for parallelization. Our experimental results with 6 real-world applications on a 12-core machine show an average parallel speedup of 4.45x and maximum speedup of 7.35x. The evaluation also includes precision results by demonstrating that our algorithm identifies significantly more inlinable indirect calls (IICs) than SUPT [15] and SS [9], two state of the art SSA-based points-to analyses implemented in LLVM.
Year
DOI
Venue
2018
10.1145/3178372.3179517
CC'18: PROCEEDINGS OF THE 27TH INTERNATIONAL CONFERENCE ON COMPILER CONSTRUCTION
Keywords
Field
DocType
Static Analysis, Pointer Analysis, Parallelism
Pointer analysis,Pointer (computer programming),Programming language,Large applications,Computer science,Parallel computing,Static analysis,Flow (psychology),Heap (data structure),Speedup,Scalability
Conference
Citations 
PageRank 
References 
3
0.38
11
Authors
3
Name
Order
Citations
PageRank
Jisheng Zhao148024.34
Michael G. Burke261079.17
Vivek Sarkar34318409.41