Liveness-Based Interprocedural Points-to Analysis

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

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:

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

1. Also referred to as ipta in the previous version of paper
2. Also referred to as lipta in the previous version of paper