Liveness-Based Interprocedural Points-to Analysis for GCC 4.6.0
Precise flow- and context-sensitive pointer analysis (FCPA)1 is considered prohibitively expensive for large programs; most tools relax one or both of the requirements for scalability. We argue that FCPA has been over-harshly judged - the vast majority of points-to pairs calculated by existing algorithms are never used by any client analysis or transformation because they involve dead variables. We therefore formulate a precise pointer analysis in terms of a joint points-to and liveness analysis which we call Liveness-based Interprocedural points-to analysis (L-FCPA)2. L-FCPA is implemented in GCC-4.6.0. It has the following features:
A short guide to applying the patch, building gcc-4.6.0 with L-FCPA, and testing L-FCPA can be found here.
The performance of L-FCPA can be contrasted against FCPA, which also effectively uses the value-based termination of call strings for interprocedural analysis, but does not limit the computation and propagation of pointer sets to live pointers and their live ranges. It is installed using the same steps as needed for L-FCPA, and the steps can be found here.
The empirical measurements were carried out on i7-960 (3.20 GHz, 16GB RAM) running on 64-bit Ubuntu. Our observations on SPEC CPU2006 and SPEC2000 benchmarks are summarized here.
L-FCPA-1.0 (for gcc 4.6.0)
FCPA-1.0 (for gcc 4.6.0)
Above code is tested with the following system configuration:
The source code of L-FCPA is distributed under GNU GPL v 2.0 or later.
For more details on data flow analysis, please refer to the book Data Flow Analysis: Theory and Practice
The Copyright of L-FCPA code is held by the GCC Resource Center of Department of Computer Science and Engineering, Indian Institute of Technology Bombay.