chord.project.analyses.rhs
Class RHSAnalysis<PE extends IEdge,SE extends IEdge>

java.lang.Object
  chord.project.analyses.JavaAnalysis
      chord.project.analyses.rhs.RHSAnalysis<PE,SE>

All Implemented Interfaces:

ITask

Direct Known Subclasses:

BackwardRHSAnalysis, ForwardRHSAnalysis

public abstract class RHSAnalysis<PE extends IEdge,SE extends IEdge>
extends JavaAnalysis

Implementation of the Reps-Horwitz-Sagiv algorithm for context-sensitive dataflow analysis.

Author:

Mayur Naik (mhn@cs.stanford.edu)

Field Summary

protected java.util.Map<joeq.Class.jq_Method,java.util.Set<joeq.Compiler.Quad.Quad>>	callersMap
protected ICICG	cicg
protected joeq.Compiler.Quad.BasicBlock	currentBB
protected joeq.Class.jq_Method	currentMethod
protected static boolean	DEBUG
protected boolean	doMerge
protected DomI	domI
protected DomM	domM
protected java.util.Map<joeq.Compiler.Quad.Quad,Location>	invkQuadToLoc
protected boolean	isForward
protected boolean	isInited
protected java.util.Map<joeq.Compiler.Quad.Inst,java.util.Set<PE>>	pathEdges
protected java.util.Map<joeq.Class.jq_Method,java.util.Set<SE>>	summEdges
protected java.util.Map<joeq.Compiler.Quad.Quad,java.util.Set<joeq.Class.jq_Method>>	targetsMap
protected java.util.List<Pair<Location,PE>>	workList

Fields inherited from class chord.project.analyses.JavaAnalysis

consumes, controls, name, produces

Constructor Summary

RHSAnalysis()

Method Summary

abstract boolean	doMerge() Determines whether this analysis should merge path edges at each program point that have the same source state but different target states and, likewise, summary edges of each method that have the same source state and different target states.
protected void	done()
abstract ICICG	getCallGraph() Provides the call graph to be used by the analysis.
abstract PE	getCopy(PE pe)
abstract PE	getInitPathEdge(joeq.Compiler.Quad.Quad q, joeq.Class.jq_Method m, PE pe)
abstract java.util.Set<Pair<Location,PE>>	getInitPathEdges()
abstract PE	getInvkPathEdge(joeq.Compiler.Quad.Quad q, PE clrPE, joeq.Class.jq_Method m, SE tgtSE)
abstract PE	getMiscPathEdge(joeq.Compiler.Quad.Quad q, PE pe)
abstract SE	getSummaryEdge(joeq.Class.jq_Method m, PE pe)
protected void	init()
abstract boolean	isForward() Determines whether this analysis is a forward analysis (as opposed to a backward analysis.
protected void	printSummaries()
protected void	runPass() Run an instance of the analysis afresh.

Methods inherited from class chord.project.analyses.JavaAnalysis

getName, run, run, setName, toString

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

protected static boolean DEBUG

workList

protected java.util.List<Pair<Location,PE extends IEdge>> workList

pathEdges

protected java.util.Map<joeq.Compiler.Quad.Inst,java.util.Set<PE extends IEdge>> pathEdges

summEdges

protected java.util.Map<joeq.Class.jq_Method,java.util.Set<SE extends IEdge>> summEdges

domI

protected DomI domI

domM

protected DomM domM

cicg

protected ICICG cicg

invkQuadToLoc

protected java.util.Map<joeq.Compiler.Quad.Quad,Location> invkQuadToLoc

callersMap

protected java.util.Map<joeq.Class.jq_Method,java.util.Set<joeq.Compiler.Quad.Quad>> callersMap

targetsMap

protected java.util.Map<joeq.Compiler.Quad.Quad,java.util.Set<joeq.Class.jq_Method>> targetsMap

isInited

protected boolean isInited

doMerge

protected final boolean doMerge

isForward

protected final boolean isForward

currentMethod

protected joeq.Class.jq_Method currentMethod

currentBB

protected joeq.Compiler.Quad.BasicBlock currentBB

Constructor Detail

RHSAnalysis

public RHSAnalysis()

Method Detail

getInitPathEdges

public abstract java.util.Set<Pair<Location,PE>> getInitPathEdges()

getInitPathEdge

public abstract PE getInitPathEdge(joeq.Compiler.Quad.Quad q,
                                   joeq.Class.jq_Method m,
                                   PE pe)

getMiscPathEdge

public abstract PE getMiscPathEdge(joeq.Compiler.Quad.Quad q,
                                   PE pe)

getInvkPathEdge

public abstract PE getInvkPathEdge(joeq.Compiler.Quad.Quad q,
                                   PE clrPE,
                                   joeq.Class.jq_Method m,
                                   SE tgtSE)

getCopy

public abstract PE getCopy(PE pe)

getSummaryEdge

public abstract SE getSummaryEdge(joeq.Class.jq_Method m,
                                  PE pe)

doMerge

public abstract boolean doMerge()

Determines whether this analysis should merge path edges at each program point that have the same source state but different target states and, likewise, summary edges of each method that have the same source state and different target states.

Returns:

true iff (path or summary) edges with the same source state and different target states should be merged.

isForward

public abstract boolean isForward()

Determines whether this analysis is a forward analysis (as opposed to a backward analysis.

Returns:

true iff this analysis is a forward analysis.

getCallGraph

public abstract ICICG getCallGraph()

Provides the call graph to be used by the analysis.

Returns:

The call graph to be used by the analysis.

done

protected void done()

init

protected void init()

runPass

protected void runPass()
                throws TimeoutException

Run an instance of the analysis afresh. Clients may call this method multiple times from their JavaAnalysis.run() method. Clients must override method getInitPathEdges() to return a new "seed" each time they call this method.

Throws:

TimeoutException

printSummaries

protected void printSummaries()