harpoon.Analysis.PointerAnalysis
Class ActionRepository

java.lang.Object
  harpoon.Analysis.PointerAnalysis.ActionRepository

All Implemented Interfaces:

Serializable

public class ActionRepository
extends Object
implements Serializable

ActionRepository merges together the alpha and pi sets from the original paper of Martin Rinard & John Whaley. More specifically, an ActionRepository maintains information about the actions executed by the analyzed part of the program (that's the meaning of alpha in the original paper) and about the ordering relation between these actions and the threads that are launched by the analyzed part (the pi structure).
Currently, only two kinds of actions are supported:

• ld - loading of a node by reading an outside edges;
• sync - synchronization (lock acquire/release) on a node.

The implementation has been specially optimized for these two types of actions and for the queries that are done for synchronization removal.
Of course, there is no problem in modifying it to support new types of actions.

Version:

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

Author:

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

See Also:

Serialized Form

Field Summary

static PANode

THIS_THREAD Fake thread node that stands for the main thread of the analyzed scope.

Constructor Summary

ActionRepository()
Creates a ActionRepository.

Method Summary

void	add_ld(PANode n1, String f, PANode n2, PANode nt, Set active_threads) Adds a ld action.
void	add_ld(Set set_n1, String f, PANode n2, PANode nt, Set active_threads) Convenient function used in the intra-procedural analysis, in the rule for a load operation.
void	add_ld(Set set_n1, String f, PANode n2, Set set_nt, Set active_threads) Convenient function used by the inter-procedural and inter-thread analysis (when a thread node can be mapped to a set of nodes).
void	add_ld(Set set_n1, String f, Set set_n2, PANode nt, Set active_threads)
void	add_ld(Set set_n1, String f, Set set_n2, Set set_nt, Set active_threads) Convenient function used by the inter-procedural and inter-thread analysis (when a load node can be mapped to a set of nodes).
void	add_sync(PASync sync, Set active_threads) Adds a sync action.
void	add_sync(Set syncs, Set active_threads) Convenient fiunction for recording a set of sync actions in parallel with all the threads from the set active_threads.
Object	clone() Produces a copy of this object.
ActionRepository	csSpecialize(Map map, CALL call)
boolean	equals(Object o) Checks the equality of two ActionRepositorys.
void	forAllActions(harpoon.Analysis.PointerAnalysis.ActionVisitor visitor) Visits all the actions from this repository.
void	forAllParActions(harpoon.Analysis.PointerAnalysis.ParActionVisitor visitor) Visits all the "parallel action" items of information from this repository (i.e. all the action || thread elements.
boolean	independent(PANode n) Checks if all the sync operation on n are independent (temporarily speaking) or not.
boolean	isSyncOn(PANode node) Checks whether any sync action is done on the node node.
void	join(ActionRepository ar2) Adds the information about actions and action-thread ordering from ar2 to this action repository.
Iterator	parallelLoads(PANode nt) Returns an iterator over the set of loads that are performed in parallel with an nt thread.
void	removeEdges(Set edges) Removes all the information related to ld actions using the edges from edges.
void	removeNodes(Set nodes) Removes all the information related to edges containing nodes from nodes.
void	show_evolution(ActionRepository ar2) Shows the evolution from ar2 to this: newly added stuff and removed stuff.
Iterator	syncsOn(PANode n, PANode nt)
String	toString() Pretty-printer for debug purposes.
ActionRepository	tSpecialize(Map map, MetaMethod run)

Methods inherited from class java.lang.Object

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

Field Detail

THIS_THREAD

public static final PANode THIS_THREAD

Fake thread node that stands for the main thread of the analyzed scope. This is used as the author thread for the actions done by the main thread of the analyzed procedure/scope, not by one of the threads it is starting.

Constructor Detail

ActionRepository

public ActionRepository()

Creates a ActionRepository.

Method Detail

show_evolution

public void show_evolution(ActionRepository ar2)

Shows the evolution from ar2 to this: newly added stuff and removed stuff. Debug purposes.

add_ld

public final void add_ld(PANode n1,
                         String f,
                         PANode n2,
                         PANode nt,
                         Set active_threads)

Adds a ld action. The thread nt read the outside edge from n1 to n2 through field f, in parallel with all the threads from active_threads.

add_ld

public final void add_ld(Set set_n1,
                         String f,
                         PANode n2,
                         PANode nt,
                         Set active_threads)

Convenient function used in the intra-procedural analysis, in the rule for a load operation. It iterates over set_n1, repeatedly calling add_ld(n1,f,n2,nt,active_threads) for each n1 in set_n1.

add_ld

public final void add_ld(Set set_n1,
                         String f,
                         PANode n2,
                         Set set_nt,
                         Set active_threads)

Convenient function used by the inter-procedural and inter-thread analysis (when a thread node can be mapped to a set of nodes). It iterates over set_nt, repeatedly calling add_ld(set_n1,f,n2,nt,active_threads) for each nt in set_nt.

add_ld

public final void add_ld(Set set_n1,
                         String f,
                         Set set_n2,
                         Set set_nt,
                         Set active_threads)

Convenient function used by the inter-procedural and inter-thread analysis (when a load node can be mapped to a set of nodes). It iterates over set_n2, repeatedly calling add_ld(set_n1,f,n2,set_nt,active_threads) for each n2 in set_n2.

add_ld

public final void add_ld(Set set_n1,
                         String f,
                         Set set_n2,
                         PANode nt,
                         Set active_threads)

add_sync

public final void add_sync(PASync sync,
                           Set active_threads)

Adds a sync action. The thread nt synchronized on n in parallel with all the threads from active_threads.

add_sync

public final void add_sync(Set syncs,
                           Set active_threads)

Convenient fiunction for recording a set of sync actions in parallel with all the threads from the set active_threads.

equals

public final boolean equals(Object o)

Checks the equality of two ActionRepositorys.

Overrides:

equals in class Object

join

public final void join(ActionRepository ar2)

Adds the information about actions and action-thread ordering from ar2 to this action repository. This method is called in the control-flow join points.

forAllActions

public final void forAllActions(harpoon.Analysis.PointerAnalysis.ActionVisitor visitor)

Visits all the actions from this repository. It calls visitor.visit_ld on the ld actions and visitor.visit_sync on the sync.

forAllParActions

public final void forAllParActions(harpoon.Analysis.PointerAnalysis.ParActionVisitor visitor)

Visits all the "parallel action" items of information from this repository (i.e. all the action || thread elements. It calls visitor.visit_par_ld or visitor.visit_par_sync according to the type of the action.

parallelLoads

public final Iterator parallelLoads(PANode nt)

Returns an iterator over the set of loads that are performed in parallel with an nt thread. O(1) time.

removeNodes

public final void removeNodes(Set nodes)

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

removeEdges

public final void removeEdges(Set edges)

Removes all the information related to ld actions using the edges from edges. edges is supposed to be a set of PAEdges.

independent

public final boolean independent(PANode n)

Checks if all the sync operation on n are independent (temporarily speaking) or not. If it returns false, two threads could synchonize on it at the same time (i.e. they can simultaneously access it); in this case, the synchonizations are really necessary and should NOT be removed.

syncsOn

public final Iterator syncsOn(PANode n,
                              PANode nt)

isSyncOn

public boolean isSyncOn(PANode node)

Checks whether any sync action is done on the node node.

csSpecialize

public final ActionRepository csSpecialize(Map map,
                                           CALL call)

tSpecialize

public final ActionRepository tSpecialize(Map map,
                                          MetaMethod run)

clone

public final Object clone()

Produces a copy of this object. The new object is totally independent from the old one: you can add/remove actions to/from it without affecting the original.

Overrides:

clone in class Object

toString

public final String toString()

Pretty-printer for debug purposes. ar1.equals(ar2) <==> ar1.toString().equals(ar2.toString()).

Overrides:

toString in class Object