harpoon.Analysis.PointerAnalysis
Class EdgeOrdering

java.lang.Object
  harpoon.Analysis.PointerAnalysis.EdgeOrdering

All Implemented Interfaces:

Serializable

public class EdgeOrdering
extends Object
implements Serializable

EdgeOrdering models the ordering relation between the inside and the outside edges belonging to the same analysis scope.
This relation records facts like this: the outside edge eo could have been read after the inside edge ei was created. This information is used in the inter-thread analysis, when outside edges are matched not only against inside edges from the opposite scope but even against inside edges from their own scope. Of course, only edges with the same field can match, so we are interested in the ordering relation only between such edges.
Although the actual implementation is fully functional, it is not a very performant one. My main concern was to make the algorithm work correctly; speed was only a second issue.

Version:

$Id: EdgeOrdering.java,v 1.4 2005/08/17 23:34:00 salcianu Exp $

Author:

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

See Also:

Serialized Form

Constructor Summary

EdgeOrdering()
Creates a EdgeOrdering object.

Method Summary

boolean	add(PAEdge eo, PAEdge ei) Adds a piece of ordering information.
boolean	add(Set nodes1, String f, PANode node2, PAEdgeSet I) Records the fact that the new outside edges <node1,f,node2> (forall node1 in nodes1) are created after all the inside edges from I.
Object	clone() Clone this object.
boolean	equals(Object o2) Checks the equality of two NodeOrdering objects.
void	forAllEntries(RelationEntryVisitor visitor) Visits all the entry of this edge ordering relation.
Iterator	getBeforeEdges(PAEdge eo) Returns an iterator over the set of the inside edges that could be already created when the inside edge eo is read.
static void	insertProjection(EdgeOrdering eo_source, EdgeOrdering eo_dest, Relation mu)
void	join(EdgeOrdering eo2) join is called in the control-flow join points.
EdgeOrdering	keepTheEssential(Set remaining_nodes) Returns a new relation containing information only about the ordering of edges between nodes from remaining_nodes.
void	removeEdges(Set edges) Removes all the information related to edges from edges.
void	removeNodes(Set nodes) Removes all the information related to edges containing nodes from nodes.
EdgeOrdering	specialize(Map map)
String	toString() String representation for debug purposes.
boolean	wasBefore(PAEdge ei, PAEdge eo) Checks whether the inside edge ei could have been created before the outside edge eo is read.

Methods inherited from class java.lang.Object

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

Constructor Detail

EdgeOrdering

public EdgeOrdering()

Creates a EdgeOrdering object.

Method Detail

add

public boolean add(PAEdge eo,
                   PAEdge ei)

Adds a piece of ordering information. More specifically, it records the following information: the outside edge eo could have been read after the inside edge ei was created.

getBeforeEdges

public Iterator getBeforeEdges(PAEdge eo)

Returns an iterator over the set of the inside edges that could be already created when the inside edge eo is read. This method will be used in the intre-thread analysis when trying to match an outside edge against those inside edges from the same scope that could be created when the load is done.

wasBefore

public boolean wasBefore(PAEdge ei,
                         PAEdge eo)

Checks whether the inside edge ei could have been created before the outside edge eo is read.

add

public boolean add(Set nodes1,
                   String f,
                   PANode node2,
                   PAEdgeSet I)

Records the fact that the new outside edges <node1,f,node2> (forall node1 in nodes1) are created after all the inside edges from I. Returns true if he edge ordering relation was changed by this addition.

join

public void join(EdgeOrdering eo2)

join is called in the control-flow join points.

forAllEntries

public void forAllEntries(RelationEntryVisitor visitor)

Visits all the entry of this edge ordering relation. In order not to add one more interface, a simple RelationEntryVisitor interface is used for the type of the argument visitor. For each outside edge eo and for each inside edge ei such that the information eo can be read after ei was created is recorded into this object, visitor.visit(eo,ei) is called.

removeNodes

public void removeNodes(Set nodes)

Removes all the information related to edges containing nodes from nodes.

removeEdges

public void removeEdges(Set edges)

Removes all the information related to edges from edges. edges must be a set of PAEdges.

clone

public Object clone()

Clone this object.

Overrides:

clone in class Object

keepTheEssential

public EdgeOrdering keepTheEssential(Set remaining_nodes)

Returns a new relation containing information only about the ordering of edges between nodes from remaining_nodes.

insertProjection

public static void insertProjection(EdgeOrdering eo_source,
                                    EdgeOrdering eo_dest,
                                    Relation mu)

specialize

public EdgeOrdering specialize(Map map)

equals

public boolean equals(Object o2)

Checks the equality of two NodeOrdering objects.

Overrides:

equals in class Object

toString

public String toString()

String representation for debug purposes.

Overrides:

toString in class Object