Class DemandRefinementPointsTo

java.lang.Object

com.ibm.wala.demandpa.alg.AbstractDemandPointsTo

com.ibm.wala.demandpa.alg.DemandRefinementPointsTo

All Implemented Interfaces:

IDemandPointerAnalysis

public class DemandRefinementPointsTo
extends AbstractDemandPointsTo

Demand-driven refinement-based points-to analysis.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	DemandRefinementPointsTo.FlowsToComputer	used to compute "flows-to sets," i.e., all the pointers that can point to some instance key
protected class	DemandRefinementPointsTo.PointsToComputer	Points-to analysis algorithm code.
static enum	DemandRefinementPointsTo.PointsToResult	Possible results of a query.

Field Summary

Fields

Modifier and Type	Field	Description
protected final IFlowGraph	g
long	lastQueryMemoryUse	to measure memory usage
protected RefinementPolicy	refinementPolicy

Fields inherited from class AbstractDemandPointsTo

cg, cha, heapModel, mam, numNodesTraversed, options

Modifier and Type	Field	Description
protected final CallGraph	cg
protected final IClassHierarchy	cha
protected final HeapModel	heapModel
protected final MemoryAccessMap	mam
protected int	numNodesTraversed
protected final AnalysisOptions	options

Method Summary

Modifier and Type	Method	Description
Pair<DemandRefinementPointsTo.PointsToResult, Collection<PointerKey>>	getFlowsTo(InstanceKeyAndState ikAndState)	get all the pointer keys that some instance key with state can flow to
Pair<DemandRefinementPointsTo.PointsToResult, Collection<PointerKey>>	getFlowsTo(InstanceKey ik)	get all the pointer keys that some instance key can flow to
Collection<InstanceKey>	getPointsTo(PointerKey pk)
Pair<DemandRefinementPointsTo.PointsToResult, Collection<InstanceKey>>	getPointsTo(PointerKey pk, Predicate<InstanceKey> ikeyPred)	compute a points-to set for a pointer key, aiming to satisfy some predicate
Collection<InstanceKeyAndState>	getPointsToWithStates(PointerKey pk)
RefinementPolicy	getRefinementPolicy()
RefinementPolicyFactory	getRefinementPolicyFactory()
StateMachineFactory<IFlowLabel>	getStateMachineFactory()
static DemandRefinementPointsTo	makeWithDefaultFlowGraph(CallGraph cg, HeapModel model, MemoryAccessMap mam, IClassHierarchy cha, AnalysisOptions options, StateMachineFactory<IFlowLabel> stateMachineFactory)	create a demand points-to analysis runner
DemandRefinementPointsTo.PointsToResult	pointsToPassesPred(PointerKey pk, Predicate<InstanceKey> ikeyPred, PointerAnalysis<InstanceKey> pa)	check if the points-to set of a variable passes some predicate, without necessarily computing the whole points-to set
void	setRefinementPolicyFactory(RefinementPolicyFactory refinementPolicyFactory)
void	setStateMachineFactory(StateMachineFactory<IFlowLabel> stateMachineFactory)
protected void	startNewQuery()	re-initialize state for a new query

Methods inherited from class AbstractDemandPointsTo

getBaseCallGraph, getClassHierarchy, getHeapModel, getNumNodesTraversed, getTraversalBudget, incrementNumNodesTraversed, setNumNodesTraversed, setTraversalBudget

Modifier and Type	Method	Description
CallGraph	getBaseCallGraph()
IClassHierarchy	getClassHierarchy()
HeapModel	getHeapModel()
int	getNumNodesTraversed()
int	getTraversalBudget()
protected void	incrementNumNodesTraversed()
protected void	setNumNodesTraversed(int traversed)
protected void	setTraversalBudget(int traversalBudget)

Methods inherited from class Object

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

Field Details

g

protected final IFlowGraph g

refinementPolicy

protected RefinementPolicy refinementPolicy

lastQueryMemoryUse

public long lastQueryMemoryUse

to measure memory usage

Method Details

getRefinementPolicy

public RefinementPolicy getRefinementPolicy()

startNewQuery

protected void startNewQuery()

re-initialize state for a new query

getPointsTo

public Pair<DemandRefinementPointsTo.PointsToResult, Collection<InstanceKey>> getPointsTo(PointerKey pk,
 Predicate<InstanceKey> ikeyPred)
                                                                                   throws IllegalArgumentException

compute a points-to set for a pointer key, aiming to satisfy some predicate

Parameters:

pk - the pointer key

ikeyPred - the desired predicate that each instance key in the points-to set should ideally satisfy

Returns:

a pair consisting of (1) a DemandRefinementPointsTo.PointsToResult indicating whether a points-to set satisfying the predicate was computed, and (2) the last computed points-to set for the variable (possibly null if no points-to set could be computed in the budget)

Throws:

IllegalArgumentException - if pk is not a LocalPointerKey; to eventually be fixed

makeWithDefaultFlowGraph

public static DemandRefinementPointsTo makeWithDefaultFlowGraph(CallGraph cg,
 HeapModel model,
 MemoryAccessMap mam,
 IClassHierarchy cha,
 AnalysisOptions options,
 StateMachineFactory<IFlowLabel> stateMachineFactory)

create a demand points-to analysis runner

Parameters:

cg - the underlying call graph for the analysis

model - the heap model to be used for the analysis

mam - indicates what code reads or writes each field

stateMachineFactory - factory for state machines to track additional properties like calling context

pointsToPassesPred

public DemandRefinementPointsTo.PointsToResult pointsToPassesPred(PointerKey pk,
 Predicate<InstanceKey> ikeyPred,
 PointerAnalysis<InstanceKey> pa)
                                                           throws IllegalArgumentException

check if the points-to set of a variable passes some predicate, without necessarily computing the whole points-to set

Parameters:

pk - the pointer key

ikeyPred - the desired predicate that each instance key in the points-to set should ideally satisfy

pa - a pre-computed points-to analysis

Returns:

a DemandRefinementPointsTo.PointsToResult indicating whether a points-to set satisfying the predicate was computed

Throws:

IllegalArgumentException - if pk is not a LocalPointerKey; to eventually be fixed

getPointsTo

public Collection<InstanceKey> getPointsTo(PointerKey pk)

Returns:

the points-to set of pk, or null if the points-to set can't be computed in the allocated budget

getPointsToWithStates

public Collection<InstanceKeyAndState> getPointsToWithStates(PointerKey pk)

Returns:

the points-to set of pk, including the StateMachine.States attached to the InstanceKeys, or null if the points-to set can't be computed in the allocated budget

getFlowsTo

public Pair<DemandRefinementPointsTo.PointsToResult, Collection<PointerKey>> getFlowsTo(InstanceKey ik)

get all the pointer keys that some instance key can flow to

Returns:

a pair consisting of (1) a DemandRefinementPointsTo.PointsToResult indicating whether a flows-to set was computed, and (2) the last computed flows-to set for the instance key (possibly null if no flows-to set could be computed in the budget)

getFlowsTo

public Pair<DemandRefinementPointsTo.PointsToResult, Collection<PointerKey>> getFlowsTo(InstanceKeyAndState ikAndState)

get all the pointer keys that some instance key with state can flow to

Returns:

a pair consisting of (1) a DemandRefinementPointsTo.PointsToResult indicating whether a flows-to set was computed, and (2) the last computed flows-to set for the instance key (possibly null if no flows-to set could be computed in the budget)

getStateMachineFactory

public StateMachineFactory<IFlowLabel> getStateMachineFactory()

setStateMachineFactory

public void setStateMachineFactory(StateMachineFactory<IFlowLabel> stateMachineFactory)

getRefinementPolicyFactory

public RefinementPolicyFactory getRefinementPolicyFactory()

setRefinementPolicyFactory

public void setRefinementPolicyFactory(RefinementPolicyFactory refinementPolicyFactory)