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 setconstraint based pointer analysis, which is flow and contextinsensitive. It accepts, as input, simple constraints of the form:
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:
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 = { g_{x},g_{y} } which means that q can target { g_{x},g_{y} } at any point in the program. An important point here is that we must derive all facts to obtain a sound solution.
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 = { g_{x},g_{y} } which means that q can target { g_{x},g_{y} } 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 HeintzTardieu [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 fieldsensitive 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.
This system was used in the experiments performed in my work on online cycle detection and difference propagation and also my other work on fieldsensitive 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: pcs2.106020401.tgz.
The version used for the PASTE paper was pcs2.129010301PASTE04.tgz. The version used for the SCAM paper was pcs1.027040301BETA2SCAM03.tgz.
The version used for the PASTE paper was pcs2.129010301PASTE04.tgz. The version used for the SCAM paper was pcs1.027040301BETA2SCAM03.tgz.
References
[HT01] 
N. Heintze and O. Tardieu. Ultrafast 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 254263, 2001.
