org.jikesrvm.compilers.opt.util
Class SpaceEffGraph

java.lang.Object
  org.jikesrvm.compilers.opt.util.SpaceEffGraph

All Implemented Interfaces:

Graph, TopSortInterface

Direct Known Subclasses:

CoalesceGraph, ControlFlowGraph, DepGraph, LSTGraph

public class SpaceEffGraph
extends Object
implements Graph, TopSortInterface

SpaceEffGraph package implements a generic directed graph that can be a multigraph. It uses Lists to model nodes and edges information.

SpaceEffGraph is a generic graph. Extend to implement specific graph types.

_firstNode

protected SpaceEffGraphNode _firstNode

First node

_lastNode

protected SpaceEffGraphNode _lastNode

Last node

_rootNodes

private SpaceEffGraphNodeListHeader _rootNodes

Nodes with no predecessors

_topSortNodes

private SpaceEffGraphNodeListHeader _topSortNodes

Topological sort order

numberOfNodes

protected int numberOfNodes

Number of nodes

forwardTopSorted

public boolean forwardTopSorted

backwardTopSorted

public boolean backwardTopSorted

SpaceEffGraph

public SpaceEffGraph()

numberOfNodes

public final int numberOfNodes()

Description copied from interface: Graph

Find out how many nodes are in the graph

Specified by:

numberOfNodes in interface Graph

Specified by:

numberOfNodes in interface TopSortInterface

Returns:

the number of nodes in the graph

setNumberOfNodes

public final void setNumberOfNodes(int n)

Set number of nodes

Parameters:

n - new number of nodes

allocateNodeNumber

public final int allocateNodeNumber()

Get the next node number

Returns:

the node number

compactNodeNumbering

public void compactNodeNumbering()

Renumber the nodes densely from 0...numberOfNodes-1.

Specified by:

compactNodeNumbering in interface Graph

enumerateNodes

public Enumeration<GraphNode> enumerateNodes()

Enumerate the nodes in no particular order

Specified by:

enumerateNodes in interface Graph

Returns:

an enumeration of all nodes in the graph

See Also:

GraphNode

startNode

public SortedGraphNode startNode(boolean forward)

Description copied from interface: TopSortInterface

Return the start node if forward = true for forward topsort, and return the end node if forward = false for backward topsort.

Specified by:

startNode in interface TopSortInterface

Parameters:

forward - whether we are viewing the graph in the forward direction

Returns:

the start node if forward = true for forward topsort, the end node if forward = false for backward topsort.

isTopSorted

public boolean isTopSorted(boolean forward)

Description copied from interface: TopSortInterface

Return true if no resetTopSorted(forward) has been executed since the last setTopSorted(forward) has been executed

Specified by:

isTopSorted in interface TopSortInterface

Parameters:

forward - whether we are viewing the graph in the forward direction

Returns:

true if no resetTopSorted(forward) has been executed since the last setTopSorted(forward) has been executed

setTopSorted

public void setTopSorted(boolean forward)

Description copied from interface: TopSortInterface

Should have a side effect such that isTopSorted(forward) returns the correct value.

Specified by:

setTopSorted in interface TopSortInterface

Parameters:

forward - whether we are viewing the graph in the forward direction

resetTopSorted

public void resetTopSorted()

Description copied from interface: TopSortInterface

Should have a side effect such that isTopSorted(forward) returns the correct value.

Specified by:

resetTopSorted in interface TopSortInterface

addGraphNode

public final void addGraphNode(GraphNode inode)

Description copied from interface: Graph

Add a new graph node to the graph.

Specified by:

addGraphNode in interface Graph

Parameters:

inode - node to add

removeGraphNode

public final void removeGraphNode(SpaceEffGraphNode node)

Remove a node from the graph.

Parameters:

node - node to remove

addGraphEdge

public void addGraphEdge(GraphNode from,
                         GraphNode to)

Add an edge to the graph.

Specified by:

addGraphEdge in interface Graph

Parameters:

from - start node

to - end node

See Also:

addGraphEdge(SpaceEffGraphEdge)

addGraphEdge

public void addGraphEdge(SpaceEffGraphEdge e)

Add an edge to the graph.

Parameters:

e - edge to insert

See Also:

addGraphEdge(GraphNode,GraphNode)

setFirstNode

public final void setFirstNode(SpaceEffGraphNode firstNode)

Reset the list of nodes of the graph. WARNING!!! Use with caution if you know what you are doing.

Parameters:

firstNode - new value of the node list

setLastNode

public final void setLastNode(SpaceEffGraphNode lastNode)

Reset the list of nodes of the graph. WARNING!!! Use with caution if you know what you are doing.

Parameters:

lastNode - new value of the node list

firstNode

public final SpaceEffGraphNode firstNode()

Get the list of nodes.

Returns:

list of nodes

lastNode

public final SpaceEffGraphNode lastNode()

Get the end of the list of nodes.

Returns:

end of the list of nodes

addRootNode

public final void addRootNode(SpaceEffGraphNode root)

Add a root node to the graph.

Parameters:

root - a node to add

rootNodes

public final SpaceEffGraphNodeList rootNodes()

Get the list of root nodes.

Returns:

list of root nodes

topSortOrder

public final SpaceEffGraphNodeList topSortOrder()

Get the topological order of nodes.

Returns:

topological order of nodes

clearDFS

public final void clearDFS()

Clear the DFS flags.

buildTopSort

public void buildTopSort()

Build a topological sort of this graph

buildRevTopSort

public SortedGraphNode buildRevTopSort()

Build a reverse topological sort of this graph

Returns:

a node if we build a new order, null if we reused the old

initTopSort

protected void initTopSort()

addTopSortNode

protected void addTopSortNode(SpaceEffGraphNode node)

topSort

public void topSort()

dfs

private void dfs(SpaceEffGraphNode node)

toString

public String toString()

Return a string representation of this graph.

Overrides:

toString in class Object

Returns:

a string representation of the graph

printDepthFirst

public void printDepthFirst()

Print, to System.out, the basic blocks in depth first order.

print

private void print(Enumeration<GraphNode> e)

Print, to System.out, the basic blocks in the order given in the supplied enumeration.

Parameters:

e - enumeration order to print blocks