org.jikesrvm.compilers.opt.util
Class SpaceEffGraphNode

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

All Implemented Interfaces:

GraphElement, GraphNode

Direct Known Subclasses:

CoalesceGraph.Node, DepGraphNode, LSTNode, SortedGraphNode, ValueGraphVertex

public class SpaceEffGraphNode
extends Object
implements GraphNode

SpaceEffGraphNode is a generic graph node. Extend this to implement specific graph node types. A node has a list of out edges and a list of in edges. We maintain both to support bidirectional traversal of the graph.

scratchObject

public Object scratchObject

scratch field: optimizations use as they wish

scratch

public int scratch

any optimization can use this for its own purposes

info

protected int info

The following word is used for various purposes. The first 8 bits are used for flags, and the remaining 24 bits for any node information (node number, for example)

DFS_VISITED

static final int DFS_VISITED

See Also:

Constant Field Values

TOP_VISITED

static final int TOP_VISITED

See Also:

Constant Field Values

ON_STACK

static final int ON_STACK

See Also:

Constant Field Values

LOOP_HEADER

static final int LOOP_HEADER

See Also:

Constant Field Values

INFO_MASK

static final int INFO_MASK

See Also:

Constant Field Values

nextSorted

public SpaceEffGraphNode nextSorted

_outEdgeStart

protected SpaceEffGraphEdge _outEdgeStart

_outEdgeEnd

protected SpaceEffGraphEdge _outEdgeEnd

_inEdgeStart

protected SpaceEffGraphEdge _inEdgeStart

_inEdgeEnd

protected SpaceEffGraphEdge _inEdgeEnd

prev

public SpaceEffGraphNode prev

Links inlined from DoublyLinkedListElement.

next

public SpaceEffGraphNode next

Links inlined from DoublyLinkedListElement.

SpaceEffGraphNode

public SpaceEffGraphNode()

dfsVisited

public final boolean dfsVisited()

topVisited

public final boolean topVisited()

onStack

public final boolean onStack()

flagsOn

public final boolean flagsOn()

isLoopHeader

public final boolean isLoopHeader()

setDfsVisited

public final void setDfsVisited()

setTopVisited

public final void setTopVisited()

setOnStack

public final void setOnStack()

setDfsVisitedOnStack

public final void setDfsVisitedOnStack()

setLoopHeader

public final void setLoopHeader()

clearDfsVisited

public final void clearDfsVisited()

clearTopVisited

public final void clearTopVisited()

clearOnStack

public final void clearOnStack()

clearFlags

public final void clearFlags()

clearLoopHeader

public final void clearLoopHeader()

getScratch

public int getScratch()

Description copied from interface: GraphElement

read the scratch field of int type

Specified by:

getScratch in interface GraphElement

Returns:

the contents of the int scratch field

setScratch

public int setScratch(int scratch)

Description copied from interface: GraphElement

set the scratch field of int type

Specified by:

setScratch in interface GraphElement

Parameters:

scratch - the new contents of the int scratch field

setNumber

public final void setNumber(int value)

getNumber

public final int getNumber()

getIndex

public final int getIndex()

Description copied from interface: GraphNode

The index of this node in its graph. In general, this can e anarbitrary number, but after a call to Graph.compactNodeNumbering the nodes of a graph should be numbered 0 thru (# of nodes in graph - 1).

Specified by:

getIndex in interface GraphNode

Returns:

the index of this node in its graph.

setIndex

public final void setIndex(int i)

Specified by:

setIndex in interface GraphNode

firstInEdge

public final SpaceEffGraphEdge firstInEdge()

firstOutEdge

public final SpaceEffGraphEdge firstOutEdge()

firstInNode

public final SpaceEffGraphNode firstInNode()

firstOutNode

public final SpaceEffGraphNode firstOutNode()

clearIn

final void clearIn()

clear the in set of edges

clearOut

final void clearOut()

clear the out set of edges

deleteIn

public final void deleteIn()

deleteOut

public final void deleteOut()

getNumberOfIn

public final int getNumberOfIn()

getNumberOfOut

public final int getNumberOfOut()

hasZeroOut

public final boolean hasZeroOut()

hasZeroIn

public final boolean hasZeroIn()

hasOneOut

public final boolean hasOneOut()

hasOneIn

public final boolean hasOneIn()

pointsIn

public final boolean pointsIn(SpaceEffGraphNode inNode)

pointsOut

public final boolean pointsOut(SpaceEffGraphNode outNode)

hasIn

public final boolean hasIn(GraphNode in)

hasOut

public final boolean hasOut(GraphNode out)

findOutEdgeTo

public final SpaceEffGraphEdge findOutEdgeTo(SpaceEffGraphNode n)

replaceInEdge

public final void replaceInEdge(SpaceEffGraphEdge e1,
                                SpaceEffGraphEdge e2)

replaces the in edge matching e1 with e2. maintains the ordering of edges

TODO YUCK: this data structure is messy. I assume this is in the name of efficiency, but it makes control flow graph manipulations a real pain. (SJF)

hasOneIn

public final boolean hasOneIn(SpaceEffGraphNode inNode)

hasOneOut

public final boolean hasOneOut(SpaceEffGraphNode outNode)

replaceOut

public final void replaceOut(SpaceEffGraphNode oldOut,
                             SpaceEffGraphNode newOut)

insertOut

public final void insertOut(SpaceEffGraphNode to,
                            SpaceEffGraphEdge e)

insertOut

public final void insertOut(SpaceEffGraphNode to)

deleteOut

public final void deleteOut(SpaceEffGraphNode node)

deleteOut

public final void deleteOut(SpaceEffGraphEdge e)

markDFN

public final void markDFN(int DFN)

markSCC

public final void markSCC(int currSCC)

sortDFS

public final void sortDFS()

_sortDFS

protected final void _sortDFS(SpaceEffGraphNode header)

clearOutFlags

public final void clearOutFlags()

clearInFlags

public final void clearInFlags()

sortTop

public final void sortTop()

_sortTop

protected final SpaceEffGraphNode _sortTop(SpaceEffGraphNode tail)

sortRevTop

public final void sortRevTop()

_sortRevTop

protected final SpaceEffGraphNode _sortRevTop(SpaceEffGraphNode tail)

printSorted

final void printSorted()

revertOuts

final void revertOuts()

Revert the sequence of out edges

inEdges

public final SpaceEffGraphNode.InEdgeEnumeration inEdges()

outEdges

public final SpaceEffGraphNode.OutEdgeEnumeration outEdges()

inNodes

public final Enumeration<GraphNode> inNodes()

Description copied from interface: GraphNode

Get an enumeration of all the edges at which edges that point to this node are sourced.

Specified by:

inNodes in interface GraphNode

Returns:

an enumeration of all the edges at which edges that point to this node are sourced.

outNodes

public final Enumeration<GraphNode> outNodes()

Description copied from interface: GraphNode

Get an enumeration of all the edges to which edges sourced at this node point.

Specified by:

outNodes in interface GraphNode

Returns:

an enumeration of all the edges to which edges sourced at this node point.

printInEdges

public void printInEdges()

printOutEdges

public void printOutEdges()

printInNodes

public void printInNodes()

printOutNodes

public void printOutNodes()

printExtended

public void printExtended()

appendInEdge

protected final void appendInEdge(SpaceEffGraphEdge e)

appendOutEdge

protected final void appendOutEdge(SpaceEffGraphEdge e)

removeIn

protected final void removeIn(SpaceEffGraphEdge InEdge)

removeIn

protected final SpaceEffGraphEdge removeIn(SpaceEffGraphNode InNode)

removeOut

protected final void removeOut(SpaceEffGraphEdge OutEdge)

removeOut

protected final SpaceEffGraphEdge removeOut(SpaceEffGraphNode OutNode)

getNext

public final SpaceEffGraphNode getNext()

Get the next node.

Returns:

next node

getPrev

public final SpaceEffGraphNode getPrev()

Get the previous node.

Returns:

previous node

append

public final void append(SpaceEffGraphNode n)

Append a given node after this node.

Parameters:

n - the node to append

remove

public final SpaceEffGraphNode remove()

Remove this node from the list.

Returns:

the next node in the list