Package com.ibm.wala.demandpa.alg

Class DemandRefinementPointsTo.PointsToComputer

java.lang.Object

com.ibm.wala.demandpa.alg.DemandRefinementPointsTo.PointsToComputer

Direct Known Subclasses:

DemandRefinementPointsTo.FlowsToComputer

Enclosing class:

DemandRefinementPointsTo

protected class DemandRefinementPointsTo.PointsToComputer
extends Object

Points-to analysis algorithm code.

Pseudocode in Chapter 5 of Manu Sridharan's dissertation.

Author:

Manu Sridharan

Field Summary

Fields

Modifier and Type	Field	Description
protected final OrdinalSetMapping<InstanceKeyAndState>	ikAndStates	for numbering InstanceKey, StateMachine.State pairs
protected final Map<PointerKeyAndState,MutableIntSet>	pkToP2Set
protected final Map<PointerKeyAndState,MutableIntSet>	pkToTrackedSet
protected final PointerKeyAndState	queriedPkAndState

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	PointsToComputer()	use this with care! only for subclasses that aren't computing points-to information exactly (e.g., DemandRefinementPointsTo.FlowsToComputer)
protected	PointsToComputer(PointerKeyAndState pkAndState)
protected	PointsToComputer(PointerKey pk)

Method Summary

Modifier and Type	Method	Description
protected boolean	addAllToP2Set(Map<PointerKeyAndState,MutableIntSet> p2setMap, PointerKeyAndState pkAndState, IntSet vals, IFlowLabel label)
protected void	addToTrackedPToWorklist(PointerKeyAndState pkAndState)
protected boolean	calleeSubGraphMissingAndShouldNotBeAdded(boolean addGraphs, CGNode callee, PointerKeyAndState pkAndState)	when doing backward interprocedural propagation, is it true that we should not add a graph representation for a callee _and_ that the subgraph for the callee is missing?
protected void	compute()
protected <K> MutableIntSet	find(Map<K,MutableIntSet> M, K key)
protected <K> MutableIntSet	findOrCreate(Map<K,MutableIntSet> M, K key)
Collection<InstanceKeyAndState>	getComputedP2Set(PointerKeyAndState queried)	get a points-to set that has already been computed via some previous call to compute(); does _not_ do any fresh demand-driven computation.
protected void	handleBackCopy(PointerKeyAndState curPkAndState, PointerKey predPk, IFlowLabel label)
void	handleTrackedPointsToWorklist()
protected boolean	handleTrackedPred(MutableIntSet curTrackedSet, PointerKeyAndState predPkAndState, IFlowLabel label)	Handle a predecessor when processing some tracked locations
void	makePassOverFieldStmts()
protected Collection<PointerKeyAndState>	matchingPToQueried(PointerKeyAndState curPkAndState, PointerKey predPk, IFlowLabel label)
protected void	worklistLoop()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

queriedPkAndState

protected final PointerKeyAndState queriedPkAndState

pkToP2Set

protected final Map<PointerKeyAndState,MutableIntSet> pkToP2Set

pkToTrackedSet

protected final Map<PointerKeyAndState,MutableIntSet> pkToTrackedSet

ikAndStates

protected final OrdinalSetMapping<InstanceKeyAndState> ikAndStates

for numbering InstanceKey, StateMachine.State pairs

Constructor Details

PointsToComputer

protected PointsToComputer()

use this with care! only for subclasses that aren't computing points-to information exactly (e.g., DemandRefinementPointsTo.FlowsToComputer)

PointsToComputer

protected PointsToComputer(PointerKey pk)

PointsToComputer

protected PointsToComputer(PointerKeyAndState pkAndState)

Method Details

getComputedP2Set

public Collection<InstanceKeyAndState> getComputedP2Set(PointerKeyAndState queried)

get a points-to set that has already been computed via some previous call to compute(); does _not_ do any fresh demand-driven computation.

addAllToP2Set

protected boolean addAllToP2Set(Map<PointerKeyAndState,MutableIntSet> p2setMap,
 PointerKeyAndState pkAndState,
 IntSet vals,
 IFlowLabel label)

compute

protected void compute()

worklistLoop

protected void worklistLoop()

matchingPToQueried

protected Collection<PointerKeyAndState> matchingPToQueried(PointerKeyAndState curPkAndState,
 PointerKey predPk,
 IFlowLabel label)

Parameters:

label - the label of the edge from curPk to predPk (must be barred)

Returns:

those PointerKeyAndStates whose points-to sets have been queried, such that the PointerKey is predPk, and transitioning from its state on label.bar() yields the state of curPkAndState

handleBackCopy

protected void handleBackCopy(PointerKeyAndState curPkAndState,
 PointerKey predPk,
 IFlowLabel label)

addToTrackedPToWorklist

protected void addToTrackedPToWorklist(PointerKeyAndState pkAndState)

calleeSubGraphMissingAndShouldNotBeAdded

protected boolean calleeSubGraphMissingAndShouldNotBeAdded(boolean addGraphs,
 CGNode callee,
 PointerKeyAndState pkAndState)

when doing backward interprocedural propagation, is it true that we should not add a graph representation for a callee _and_ that the subgraph for the callee is missing?

Parameters:

addGraphs - whether graphs should always be added

handleTrackedPointsToWorklist

public void handleTrackedPointsToWorklist()

makePassOverFieldStmts

public void makePassOverFieldStmts()

findOrCreate

protected <K> MutableIntSet findOrCreate(Map<K,MutableIntSet> M,
 K key)

find

protected <K> MutableIntSet find(Map<K,MutableIntSet> M,
 K key)

handleTrackedPred

protected boolean handleTrackedPred(MutableIntSet curTrackedSet,
 PointerKeyAndState predPkAndState,
 IFlowLabel label)

Handle a predecessor when processing some tracked locations

Parameters:

curTrackedSet - the tracked locations

predPkAndState - the predecessor