Precise flow- and context-sensitive pointer analysis (FCPA)¹ 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)². L-FCPA is implemented in GCC-4.6.0. It has the following features:

• Points-to information is computed only for the live pointers and its propagation is sparse (restricted to live ranges of respective pointers)
• It uses strong liveness, effectively including dead code elimination
• Calculates must-points-to information from may-pointsto-information instead of using a mutual fixed-point
• Uses value-based termination of call strings during interprocedural analysis

Installing L-FCPA

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.

Empirical Measurements

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.

Releases

L-FCPA-1.0 (for gcc 4.6.0)

• Download Patch

FCPA-1.0 (for gcc 4.6.0)

• Download Patch

Prerequisites

Above code is tested with the following system configuration:

• Operating System: Ubuntu 11.04 Natty Release
• Native compiler: Gnu Compiler collection (GCC) 4.x

Source Code

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.