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 have formulated a joint points-to and liveness analysis which we call Liveness-based Interprocedural points-to analysis (LFCPA)² and have implemented it in GCC-4.6.0. It has the following features:

• Points-to information is computed only for pointers that are live and its propagation is restricted to live ranges of respective pointers
• Instead of simple liveness, strong liveness is used, effectively incorporating the effect of dead code elimination
• Must-points-to information is calculated from may-pointsto-information instead of using a mutual fixed-point computation
• An efficient variant of call strings method that terminates call string construction using data flow values is used for fully flow and context sensitive interprocedural analysis

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.

Future work: Current LFCPA implementation is a naive implementation using linked lists and linear search and was primarily aimed at meausuring precision. The four main tasks that we plan to undertake are: (a) Efficient data structures for scalability, (b) Extensions for precise heap analysis, (c) Incremental version, and (d) Using flow sensitive points-to information in other passes of GCC.

LFCPA Release:

• For gcc-4.7.2 : plugin and instructions.
• For gcc-4.6.2 : plugin and instructions

Documentation on LFCPA: (a) Pre-print copy of the paper published in SAS 2012, (b) associated slides, and (c) slides on value based termination of call strings.

Prerequisites: This code has been tested with Ubuntu 11.04 Natty Release and the default gcc available with it.

License: The source code of LFCPA 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 LFCPA code is held by the GCC Resource Center of Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

Credits: LFCPA implementation has been done by Prashant Singh Rawat and its dynamic plugins have been created by Sudakshina Das