SpaceEffGraph (Jikes RVM API)

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.

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

private static class SpaceEffGraph.NodeEnumeration

Nested Classes
Modifier and Type	Class and Description
`private static class`	`SpaceEffGraph.NodeEnumeration`

Field Summary

Fields
Modifier and Type	Field and Description
`protected SpaceEffGraphNode`	`_firstNode` First node
`protected SpaceEffGraphNode`	`_lastNode` Last node
`private SpaceEffGraphNodeListHeader`	`_rootNodes` Nodes with no predecessors
`private SpaceEffGraphNodeListHeader`	`_topSortNodes` Topological sort order
`boolean`	`backwardTopSorted`
`boolean`	`forwardTopSorted`
`protected int`	`numberOfNodes` Number of nodes

Constructor Summary

Constructors
Constructor and Description

SpaceEffGraph()

Constructors
Constructor and Description
`SpaceEffGraph()`

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`addGraphEdge(GraphNode from, GraphNode to)` Add an edge to the graph.
`void`	`addGraphEdge(SpaceEffGraphEdge e)` Add an edge to the graph.
`void`	`addGraphNode(GraphNode inode)` Add a new graph node to the graph.
`void`	`addRootNode(SpaceEffGraphNode root)` Add a root node to the graph.
`protected void`	`addTopSortNode(SpaceEffGraphNode node)`
`int`	`allocateNodeNumber()` Get the next node number
`SortedGraphNode`	`buildRevTopSort()` Build a reverse topological sort of this graph
`void`	`buildTopSort()` Build a topological sort of this graph
`void`	`clearDFS()` Clear the DFS flags.
`void`	`compactNodeNumbering()` Renumber the nodes densely from 0...numberOfNodes-1.
`private void`	`dfs(SpaceEffGraphNode node)`
`Enumeration<GraphNode>`	`enumerateNodes()` Enumerate the nodes in no particular order
`SpaceEffGraphNode`	`firstNode()` Get the list of nodes.
`protected void`	`initTopSort()`
`boolean`	`isTopSorted(boolean forward)` Return true if no resetTopSorted(forward) has been executed since the last setTopSorted(forward) has been executed
`SpaceEffGraphNode`	`lastNode()` Get the end of the list of nodes.
`int`	`numberOfNodes()` Find out how many nodes are in the graph
`private void`	`print(Enumeration<GraphNode> e)` Print, to System.out, the basic blocks in the order given in the supplied enumeration.
`void`	`printDepthFirst()` Print, to System.out, the basic blocks in depth first order.
`void`	`removeGraphNode(SpaceEffGraphNode node)` Remove a node from the graph.
`void`	`resetTopSorted()` Should have a side effect such that isTopSorted(forward) returns the correct value.
`SpaceEffGraphNodeList`	`rootNodes()` Get the list of root nodes.
`void`	`setFirstNode(SpaceEffGraphNode firstNode)` Reset the list of nodes of the graph.
`void`	`setLastNode(SpaceEffGraphNode lastNode)` Reset the list of nodes of the graph.
`void`	`setNumberOfNodes(int n)` Set number of nodes
`void`	`setTopSorted(boolean forward)` Should have a side effect such that isTopSorted(forward) returns the correct value.
`SortedGraphNode`	`startNode(boolean forward)` Return the start node if forward = true for forward topsort, and return the end node if forward = false for backward topsort.
`void`	`topSort()`
`SpaceEffGraphNodeList`	`topSortOrder()` Get the topological order of nodes.
`String`	`toString()` Return a string representation of this graph.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Field Detail
  - _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
```
- Constructor Detail
  - SpaceEffGraph
```
public SpaceEffGraph()
```
- Method Detail
  - 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

Class SpaceEffGraph

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

_firstNode

_lastNode

_rootNodes

_topSortNodes

numberOfNodes

forwardTopSorted

backwardTopSorted

Constructor Detail

SpaceEffGraph

Method Detail

numberOfNodes

setNumberOfNodes

allocateNodeNumber

compactNodeNumbering

enumerateNodes

startNode

isTopSorted

setTopSorted

resetTopSorted

addGraphNode

removeGraphNode

addGraphEdge

addGraphEdge

setFirstNode

setLastNode

firstNode

lastNode

addRootNode

rootNodes

topSortOrder

clearDFS

buildTopSort

buildRevTopSort

initTopSort

addTopSortNode

topSort

dfs

toString

printDepthFirst

print