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 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: A dynamic plugin and instructions on how to install and use it are available.
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 plugin has been created by Sudakshina Das