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:

  • 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:

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

Tested on Firefox version 3.0.8 and above     |    Site designed and maintained by GRC    |    © 2013, GCC Resource Center