> Home  

Application Description 
Pointsto analysis is a compiler technique aimed at identifying which variables/objects are pointed by the pointers of the input program. The results of this compiler phase are useful for program optimization, program verification, debugging and whole program comprehension. The algorithm presented here is a parallel implementation of the context and flow insensitive, inclusionbased, pointsto analysis described by Ben Hardekopf in his PLDI'07 paper [1]. We also implemented some techniques (HVN, HRU) described in later work [2]. [1] Ben Hardekopf and Calvin Lin. The Ant and the Grasshopper: Fast and Accurate Pointer Analysis for Millions of Lines of Code. PLDI 2007. [2] Ben Hardekopf and Calvin Lin. Exploiting Pointer and Location Equivalence to Optimize Pointer Analysis. SAS 2007. 
Algorithm 
The input for the pointsto algorithm is the program to be analyzed. The output is a map from program pointers to the set of variables they might point to. The analysis proceeds as follows:
01 foreach (variable v: wl) 02 foreach (variable w : copy neighbors of v) 03 apply copy_rule(v,w) 04 // copy rule might add a new pointsto edge to another variable x 05 if (pointsto edge added to x) 06 wl.add(x) 07 foreach (variable w : load neighbors of v) 08 apply load_rule(v, w) 09 // load rule might add a new copy edge to another variable x 10 if (copy edge added to x) 11 wl.add(x) 12 foreach (variable w : store neighbors of v) 13 apply store_rule(v,w) 14 // store rule might add a new copy edge to another variable x 15 if (copy edge added to x) 16 wl.add(x)Eventually, the algorithm will reach a fixpoint (=the worklist of active nodes is empty), so we can read the solution out of the pointsto edges of the graph. Example: A program written in C contains only the statements b=&w;b=&v;a=b;. Because there are three pointer statements and another three variables, we initialize (figure below, leftmost subfigure) the constraint graph by adding three nodes and edges. The edges are labeled with their type: p means "pointsto", while c means "copy". Then we apply the copy rule (lines 0206) twice to reach fixpoint (rightmost subfigure). From the final graph we can infer that the pointsto of both a and b is {v,w}. 
Data Structures 
There are two key data structures:

Parallelism 
The parallel (inclusionbased) pointsto analysis does not require the "full power" of a transactional memory system in order to preserve the sequential semantics, but is not an embarrasingly parallel algorithm either. As long as the multigraph supports concurrent accesses, there is a guarantee that the parallel analysis will reach the same fixpoint as the sequential implementation. In other words, we can apply the graph rewrite rules in any other and the final result will be identical to that of the sequential code (again, assuming that edges additions and the merging of nodes appear to be atomic) The parallelism intensity of the parallel algorithm is 100%, since all the active nodes in the worklist can be safely processed in parallel at any point during execution. 
Download and usage 
You can download our parallel implementation from here. (note: the file size is close to 150MB). The system requirements are identical to those of the Galois system. To analyze the gcc benchmark using two threads and a heap size of 1 gigabyte, run the following commands from the installation directory: export TEST=gcc;export PROP=apps/hardekopfPointsTo/conf/${TEST}.properties;export MEM=1g;export THREADS=2 ant clean distapp Dapp=hardekopfPointsTo ./scripts/galois d m ${MEM} f ${PROP} t ${THREADS} hardekopfPointsTo.main.MainYou should see the parallel analysis running once. The output is verified at the end of the run. If you want to analyze any of the other input programs included in the distribution (input/hardekopfPointsTo directory), simply update the TEST variable. Same applies if you want to use a different heap size, or number of threads. For instance, if we want to analyze linux using sixteen threads and a heap of 4 gigabytes, we would first type: export TEST=linux;export PROP=apps/hardekopfPointsTo/conf/${TEST}.properties;export MEM=4g;export THREADS=16The other two commands remain the same. Commandline options for Galois (number of runs, JVM tuning, etc) are listed in the manual. 