Package com.tonic.analysis.pdg

Class PDG

java.lang.Object

com.tonic.analysis.pdg.PDG

public class PDG
extends Object

Program dependence graph for a single method, holding the control and data dependence edges between its instruction nodes along with lookup indexes by instruction, value and block.

Constructor Summary

Constructors

Constructor	Description
PDG(IRMethod method)	Creates an empty graph for the given method.

Method Summary

Modifier and Type	Method	Description
void	addEdge(PDGEdge edge)	Adds an edge if not already present and links it into both endpoints.
void	addEdge(PDGNode source, PDGNode target, PDGDependenceType type)	Adds a dependence edge between two nodes.
void	addEdge(PDGNode source, PDGNode target, PDGDependenceType type, SSAValue dependentValue)	Adds a dependence edge carrying the value that induced it.
void	addNode(PDGNode node)	Adds a node if not already present, indexing it by instruction, defined value and block.
int	allocateNodeId()	Hands out the next node id and advances the counter.
Set<PDGNode>	getAllDependentOn(PDGNode node)	Finds every node reachable from the given node over one outgoing edge, of any kind.
Set<PDGNode>	getAllSources(PDGNode node)	Finds every node reaching the given node over one incoming edge, of any kind.
Map<IRBlock,List<PDGNode>>	getBlockToNodes()
List<PDGEdge>	getControlDependenceEdges()
Set<PDGNode>	getControlDependentOn(PDGNode node)	Finds the nodes whose execution is controlled by the given node.
int	getControlEdgeCount()
Set<PDGNode>	getControllingNodes(PDGNode node)	Finds the nodes that control whether the given node executes.
List<PDGEdge>	getDataDependenceEdges()
Set<PDGNode>	getDataDependentOn(PDGNode node)	Finds the nodes that consume values produced by the given node.
int	getDataEdgeCount()
Set<PDGNode>	getDataSources(PDGNode node)	Finds the nodes producing the values the given node consumes.
int	getEdgeCount()
List<PDGEdge>	getEdges()
List<PDGEdge>	getEdgesByType(PDGDependenceType type)	Collects every edge of a given dependence kind.
PDGRegionNode	getEntryNode()
PDGRegionNode	getExitNode()
PDGNode	getInstructionNode(IRInstruction instruction)	Alias for getNodeForInstruction(IRInstruction).
Map<IRInstruction,PDGInstructionNode>	getInstructionToNode()
IRMethod	getMethod()
String	getMethodName()
int	getNextNodeId()
PDGNode	getNode(int id)	Searches the node list for a given id.
int	getNodeCount()
PDGNode	getNodeForInstruction(IRInstruction instruction)	Looks up the node built for an instruction.
PDGNode	getNodeForValue(SSAValue value)	Looks up the node that defines a value.
List<PDGNode>	getNodes()
List<PDGNode>	getNodesByType(PDGNodeType type)	Collects every node of a given kind.
List<PDGNode>	getNodesInBlock(IRBlock block)	Lists the nodes built from a block, in insertion order.
List<PDGNode>	getNodesOfType(PDGNodeType type)	Alias for getNodesByType(PDGNodeType).
Map<SSAValue,PDGNode>	getValueToNode()
boolean	hasEntryNode()
void	removeEdge(PDGEdge edge)	Removes an edge and unlinks it from both endpoints.
void	setEntryNode(PDGRegionNode entryNode)	Sets the region node all top-level statements are control dependent on.
void	setExitNode(PDGRegionNode exitNode)	Sets the region node representing method exit.
String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

PDG

public PDG(IRMethod method)

Creates an empty graph for the given method.

Parameters:

method - the method this graph describes

Method Detail

getMethod

public IRMethod getMethod()

Returns:

the method

getMethodName

public String getMethodName()

Returns:

the method name

getEntryNode

public PDGRegionNode getEntryNode()

Returns:

the entry node

getExitNode

public PDGRegionNode getExitNode()

Returns:

the exit node

getInstructionToNode

public Map<IRInstruction,PDGInstructionNode> getInstructionToNode()

Returns:

the instruction to node

getValueToNode

public Map<SSAValue,PDGNode> getValueToNode()

Returns:

the value to node

getBlockToNodes

public Map<IRBlock,List<PDGNode>> getBlockToNodes()

Returns:

the block to nodes

getNextNodeId

public int getNextNodeId()

Returns:

the next node id

allocateNodeId

public int allocateNodeId()

Hands out the next node id and advances the counter.

Returns:

the allocated node id

setEntryNode

public void setEntryNode(PDGRegionNode entryNode)

Sets the region node all top-level statements are control dependent on.

Parameters:

entryNode - the entry region node

setExitNode

public void setExitNode(PDGRegionNode exitNode)

Sets the region node representing method exit.

Parameters:

exitNode - the exit region node

addNode

public void addNode(PDGNode node)

Adds a node if not already present, indexing it by instruction, defined value and block.

Parameters:

node - the node to add

addEdge

public void addEdge(PDGEdge edge)

Adds an edge if not already present and links it into both endpoints.

Parameters:

edge - the edge to add

addEdge

public void addEdge(PDGNode source,
                    PDGNode target,
                    PDGDependenceType type)

Adds a dependence edge between two nodes.

Parameters:

source - the node depended upon

target - the dependent node

type - the kind of dependence

addEdge

public void addEdge(PDGNode source,
                    PDGNode target,
                    PDGDependenceType type,
                    SSAValue dependentValue)

Adds a dependence edge carrying the value that induced it.

Parameters:

source - the node depended upon

target - the dependent node

type - the kind of dependence

dependentValue - the value flowing along the edge

removeEdge

public void removeEdge(PDGEdge edge)

Removes an edge and unlinks it from both endpoints.

Parameters:

edge - the edge to remove

getNodeForInstruction

public PDGNode getNodeForInstruction(IRInstruction instruction)

Looks up the node built for an instruction.

Parameters:

instruction - the instruction to look up

Returns:

the node, or null if the instruction has none

getNodeForValue

public PDGNode getNodeForValue(SSAValue value)

Looks up the node that defines a value.

Parameters:

value - the SSA value to look up

Returns:

the defining node, or null if the value has none

getNodesInBlock

public List<PDGNode> getNodesInBlock(IRBlock block)

Lists the nodes built from a block, in insertion order.

Parameters:

block - the block to query

Returns:

the nodes in that block, empty if none

getNodesByType

public List<PDGNode> getNodesByType(PDGNodeType type)

Collects every node of a given kind.

Parameters:

type - the node kind to match

Returns:

the matching nodes

getEdgesByType

public List<PDGEdge> getEdgesByType(PDGDependenceType type)

Collects every edge of a given dependence kind.

Parameters:

type - the dependence kind to match

Returns:

the matching edges

getControlDependenceEdges

public List<PDGEdge> getControlDependenceEdges()

Returns:

every control dependence edge in the graph

getDataDependenceEdges

public List<PDGEdge> getDataDependenceEdges()

Returns:

every data dependence edge in the graph

getControlDependentOn

public Set<PDGNode> getControlDependentOn(PDGNode node)

Finds the nodes whose execution is controlled by the given node.

Parameters:

node - the controlling node

Returns:

the nodes control dependent on it

getControllingNodes

public Set<PDGNode> getControllingNodes(PDGNode node)

Finds the nodes that control whether the given node executes.

Parameters:

node - the dependent node

Returns:

the nodes it is control dependent on

getDataDependentOn

public Set<PDGNode> getDataDependentOn(PDGNode node)

Finds the nodes that consume values produced by the given node.

Parameters:

node - the producing node

Returns:

the nodes data dependent on it

getDataSources

public Set<PDGNode> getDataSources(PDGNode node)

Finds the nodes producing the values the given node consumes.

Parameters:

node - the consuming node

Returns:

the nodes it is data dependent on

getAllDependentOn

public Set<PDGNode> getAllDependentOn(PDGNode node)

Finds every node reachable from the given node over one outgoing edge, of any kind.

Parameters:

node - the node to query

Returns:

the immediate successors

getAllSources

public Set<PDGNode> getAllSources(PDGNode node)

Finds every node reaching the given node over one incoming edge, of any kind.

Parameters:

node - the node to query

Returns:

the immediate predecessors

getNodeCount

public int getNodeCount()

Returns:

the number of nodes

getEdgeCount

public int getEdgeCount()

Returns:

the number of edges

getControlEdgeCount

public int getControlEdgeCount()

Returns:

the number of control dependence edges

getDataEdgeCount

public int getDataEdgeCount()

Returns:

the number of data dependence edges

getNodes

public List<PDGNode> getNodes()

Returns:

an unmodifiable view of the nodes

getEdges

public List<PDGEdge> getEdges()

Returns:

an unmodifiable view of the edges

hasEntryNode

public boolean hasEntryNode()

Returns:

whether an entry node has been set

getNode

public PDGNode getNode(int id)

Searches the node list for a given id.

Parameters:

id - the node id

Returns:

the node, or null if no node carries that id

getNodesOfType

public List<PDGNode> getNodesOfType(PDGNodeType type)

Alias for getNodesByType(PDGNodeType).

Parameters:

type - the node kind to match

Returns:

the matching nodes

getInstructionNode

public PDGNode getInstructionNode(IRInstruction instruction)

Alias for getNodeForInstruction(IRInstruction).

Parameters:

instruction - the instruction to look up

Returns:

the node, or null if the instruction has none

toString

public String toString()

Overrides:

toString in class Object