harpoon.Analysis.PointerAnalysis
Class PointsToGraph

java.lang.Object
  harpoon.Analysis.PointerAnalysis.PointsToGraph

All Implemented Interfaces:

Serializable, Cloneable

public class PointsToGraph
extends Object
implements Cloneable, Serializable

PointsToGraph models the memory, as specified by the abstraction of the object creation sites. Each "node" in our abstraction models one or moree objects and the graph of concrete objects is modelled as a graph of nodes. In addition, we preserve some escape information. Look into one of Martin and John Whaley papers for the complete definition.

Version:

$Id: PointsToGraph.java,v 1.11 2005/08/17 23:34:01 salcianu Exp $

Author:

Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>

See Also:

Serialized Form

Field Summary

static boolean	DEBUG
PAEscapeFunc	e The escape function.
Set	excp The set of objects which are returned as exception
PAEdgeSet	I The set of the inside edges.
PAEdgeSet	O The set of the outside edges.
Set	r The set of normally returned objects
Set	reachable_from_excp

Constructor Summary

PointsToGraph()
Creates a PointsToGraph.

Method Summary

boolean	captured(PANode node) Tests whether node node is captured.
Object	clone() Deep copy of a PointsToGraph.
boolean	equals(Object o) Checks the equality of two PointsToGraphs.
boolean	escaped(PANode node) Tests whether node node is an escaped node.
void	flushCaches() Flushes the internal caches in this PointsToGraph.
Set	getReachableFromExcp() Returns the set of nodes reachable from the exceptionally returned nodes (including the exceptionally returned nodes).
Set	getReachableFromR() Returns the set of nodes reachable from the returned nodes (including the returned nodes).
void	insert_edges(PAEdgeSet O2, PAEdgeSet I2, Relation mu)
void	insert(PointsToGraph G2, Relation mu, boolean principal, Set noholes) Inserts the image of G2 points-to graph through the mu node mapping into this object.
void	join(PointsToGraph G2) join is called in the control-flow join points.
PointsToGraph	keepTheEssential(PANode[] params, Set remaining_nodes, boolean is_main) Produces a PointsToGraph containing just the nodes that are reachable from root nodes: the nodes that could be reached from outside code (e.g. the caller): the parameter nodes (received in the params) and the returned nodes (found in this.r).
void	propagate() Convenient function that recomputes all the escape info.
void	propagate(Collection escaped) Propagates the escape information along the edges.
Set	reachableNodes(Set roots) Computes the set of nodes reachable from nodes in roots through paths that use inside and outside edges.
void	remove(Set set) Remove all the PANodes that appear in set from this points-to graph.
PointsToGraph	specialize(Map map)
String	toString() Pretty-print function for debug purposes.
boolean	willEscape(PANode node) Checks whether node node will escape because it is returned or because it is reachable from a returned node.

Methods inherited from class java.lang.Object

finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

DEBUG

public static boolean DEBUG

O

public PAEdgeSet O

The set of the outside edges.

I

public PAEdgeSet I

The set of the inside edges.

e

public PAEscapeFunc e

The escape function.

r

public Set r

The set of normally returned objects

excp

public Set excp

The set of objects which are returned as exception

reachable_from_excp

public Set reachable_from_excp

Constructor Detail

PointsToGraph

public PointsToGraph()

Creates a PointsToGraph.

Method Detail

flushCaches

public void flushCaches()

Flushes the internal caches in this PointsToGraph.

reachableNodes

public final Set reachableNodes(Set roots)

Computes the set of nodes reachable from nodes in roots through paths that use inside and outside edges. The argument must be a set of PANodes. The roots set is included in the returned set (i.e. 0-length paths are considered).

getReachableFromR

public Set getReachableFromR()

Returns the set of nodes reachable from the returned nodes (including the returned nodes).

getReachableFromExcp

public Set getReachableFromExcp()

Returns the set of nodes reachable from the exceptionally returned nodes (including the exceptionally returned nodes).

willEscape

public boolean willEscape(PANode node)

Checks whether node node will escape because it is returned or because it is reachable from a returned node. Both kinds of returns - return and throw - are considered.

escaped

public boolean escaped(PANode node)

Tests whether node node is an escaped node. An escaped node is a node which has escaped through some node or method hole or is reachable (possibly through a 0-length path) from a node which is returned as a normal result or as an exception, from the method.

captured

public boolean captured(PANode node)

Tests whether node node is captured. This method is simply the negation of escaped.

join

public void join(PointsToGraph G2)

join is called in the control-flow join points.

remove

public void remove(Set set)

Remove all the PANodes that appear in set from this points-to graph.

insert

public void insert(PointsToGraph G2,
                   Relation mu,
                   boolean principal,
                   Set noholes)

Inserts the image of G2 points-to graph through the mu node mapping into this object. This method is designed to be called - indirectly through ParIntGraph.insertAllButArEo - at the end of the caller/callee or starter/startee interaction.
principal controls whether the return and exception set are inserted.

insert_edges

public void insert_edges(PAEdgeSet O2,
                         PAEdgeSet I2,
                         Relation mu)

specialize

public PointsToGraph specialize(Map map)

propagate

public void propagate(Collection escaped)

Propagates the escape information along the edges.

propagate

public void propagate()

Convenient function that recomputes all the escape info. Equivalent to propagate(e.escapedNodes()).

equals

public boolean equals(Object o)

Checks the equality of two PointsToGraphs.

Overrides:

equals in class Object

clone

public Object clone()

Deep copy of a PointsToGraph.

Overrides:

clone in class Object

keepTheEssential

public PointsToGraph keepTheEssential(PANode[] params,
                                      Set remaining_nodes,
                                      boolean is_main)

Produces a PointsToGraph containing just the nodes that are reachable from root nodes: the nodes that could be reached from outside code (e.g. the caller): the parameter nodes (received in the params) and the returned nodes (found in this.r). The static nodes are implicitly considered roots for all the methods except "main" (is_main=true).
In addition to returning the new, reduced graph, this method builds the set of nodes that are in the new graph. This set is put in remaining_nodes

toString

public String toString()

Pretty-print function for debug purposes. Two equal PointsToGraphs are guaranteed to have the same string representation.

Overrides:

toString in class Object