Parallel Pointer Analysis with CFL-Reachability
Authors:
- Yu SuYSYu Su
- Ding YeDYDing Ye
- Jingling XueJXJingling Xue
- 1 September 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01903918,p. 451-460
Abstract
This paper presents the first parallel implementation of pointer analysis with Context-Free Language (CFL) reachability, an important foundation for supporting demand queries in compiler optimisation and software engineering. Formulated as a graph traversal problem (often with context- and field-sensitivity for desired precision) and driven by queries (issued often in batch mode), this analysis is non-trivial to parallelise. We introduce a parallel solution to the CFL-reachability-based pointer analysis, with context- and field-sensitivity. We exploit its inherent parallelism by avoiding redundant graph traversals with two novel techniques, data sharing and query scheduling. With data sharing, paths discovered in answering a query are recorded as shortcuts so that subsequent queries will take the shortcuts instead of re-traversing its associated paths. With query scheduling, queries are prioritised according to their statically estimated dependences so that more redundant traversals can be further avoided. Evaluated using a set of 20 Java programs, our parallel implementation of CFL-reachability-based pointer analysis achieves an average speedup of 16.2X over a state-of-the-art sequential implementation on 16 CPU cores.Keywords
This publication has 14 references indexed in Scilit:
- Time- and space-efficient flow-sensitive points-to analysisACM Transactions on Architecture and Code Optimization, 2013
- Exploring hybrid memory for GPU energy efficiency through software-hardware co-design2013
- Fast and precise points-to analysis with incremental CFL-reachability summarisation: preliminary experience2012
- On-demand dynamic summary-based points-to analysis2012
- Efficient Parallel Graph Exploration on Multi-Core CPU and GPU2011
- EigenCFA2011
- Parallel points-to analysis for multi-core machines2011
- Demand-driven alias analysis for C2008
- A Parallel External-Memory Frontier Breadth-First Traversal Algorithm for Clusters of Workstations2006
- Program analysis via graph reachabilityInformation and Software Technology, 1998