PCS is an experimental system for performing pointer analysis, which I have been using to test out various new algorithms and technqiues.

Contents

Introduction

The Pointer Constraint System provides a set-constraint based pointer analysis, which is flow- and context-insensitive. It accepts, as input, simple constraints of the form:

inference system

Where p and q are constraint variables and * is the usual dereference operator. We can think of each variable as containing the set of variables it points to. To perform the analysis we translate the source program into this language, by compiling with scc and running the suifcgen tool which accompanies the PCS distribution. For example, consider the following where the solution (shown below the line) is obtained using the inference rules of Figure 1:

int *f(int *p) {
  return p;(1)  
}
int g() {
  int x,y,*p,*q,**r,**s;
  s=&p; (2)  
  if(...) p=&x; (3)  
  else p=&y; (4)  
  r=s;(5)  
  q=f(*r);(6)  
}(7)  

(8)    
(9)    
(10)    
(11)    
(12)    
(13)    
(14)    
(15)    



Figure 1. An inference system for pointer analysis


Notice that variable names are augmented with scope information to ensure their uniqueness. From the derivation, we can build the target set of a variable v by collecting all constraints of the form v { x }. Thus, in the example, constraints 14+15 give q = { gx,gy } which means that q can target { gx,gy } at any point in the program. An important point here is that we must derive all facts to obtain a sound solution.

Details

The current version implements two different solving algorithms: worklist and Heintz-Tardieu [HT01]. In addition, the distribution contains several ways of customizing the worklist algorithm. In particular, there are components for online cycle detection, difference propagation and iteration order.

This system was used in the experiments performed in my work on online cycle detection and difference propagation and also my other work on field-sensitive pointer analysis for C. Finally, the system is written in C++ and makes extensive use of the STL (see e.g. SGI's page) and the BOOST library.

Download

The current version of the distribution is: pcs-2.1-060204-01.tgz.
The version used for the PASTE paper was pcs-2.1-290103-01-PASTE04.tgz. The version used for the SCAM paper was pcs-1.0-270403-01-BETA2-SCAM03.tgz.

References

[HT01]
N. Heintze and O. Tardieu. Ultra-fast aliasing analysis using CLA: A million lines of C code in a second. In Proceedings of the ACM Conference on Programming Language Design and Implementation, pages 254-263, 2001.