org.jikesrvm.compilers.opt.util

Class SortedGraphIterator

java.lang.Object

org.jikesrvm.compilers.opt.util.SortedGraphIterator

public class SortedGraphIterator
extends Object

An efficient topsort dataflow iterator to be used with SortedGraphNode. The graph represents entities (values, statements, block, etc) to analyze and the graph makes explicit the data-flow dependencies between them. Fixed-point iteration is expressed using a special iterator that takes a parameter denoting whether analysis of the current element changed the data-flow result. If not, the iterator continues thru other unanalyzed elements. If there is a change, then the data-flow successors of the current node become the new head of the order of remaining nodes.

A typical use is as follows:

   BasicBlock start = ir.cfg.entry();
   SortedGraphIterator bbIter = new SortedGraphIterator(start, true);
   // true means forward analysis; false means backward analysis
   for (BasicBlock currBlock = start; currBlock!= null;) {

       // do your analysis of the currBlock here

       boolean changed = ... // true if the solution of currBlock has been changed since
                             // the last visit of currBlock.
                             // false if not.

       currBlock = (BasicBlock) bbIter.markAndGetNextTopSort(changed);
  }

Field Summary

Fields

Modifier and Type	Field and Description
protected SortedGraphNode	barrier The earliest place where we needed to move currentNode back in the list because its successor needed to be processed.
protected int	changeMark A unique marker to use to mark nodes
protected SortedGraphNode	currentNode The current node we are processing
protected boolean	forward The direction we are moving on the graph

Constructor Summary

Constructors

Constructor and Description
SortedGraphIterator(SortedGraphNode current, boolean forward) Constructor

Method Summary

Modifier and Type	Method and Description
private void	advanceBarrier() This method keeps track of nodes in the graph that are known to not have been visited yet even once.
boolean	isSinglePredecessor(SortedGraphNode currentNode, SortedGraphNode nextNode) This method checks to see if the second parameter has a single successor, which is the first parameter.
boolean	isSingleSuccessor(SortedGraphNode currentNode, SortedGraphNode nextNode) This method checks to see if the second parameter has a single predecessor, which is the first parameter.
SortedGraphNode	markAndGetNextTopSort(boolean changed) General fixed-pointer iterator; call this repeatedly until there is no more work to do.

Methods inherited from class java.lang.Object

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

Field Detail

barrier

protected SortedGraphNode barrier

The earliest place where we needed to move currentNode back in the list because its successor needed to be processed.

changeMark

protected int changeMark

A unique marker to use to mark nodes

currentNode

protected SortedGraphNode currentNode

The current node we are processing

forward

protected boolean forward

The direction we are moving on the graph

Constructor Detail

SortedGraphIterator

public SortedGraphIterator(SortedGraphNode current,
                           boolean forward)

Constructor

Parameters:

current - the node to start the iteration at

forward - the direction we are processing the graph

Method Detail

markAndGetNextTopSort

public SortedGraphNode markAndGetNextTopSort(boolean changed)

General fixed-pointer iterator; call this repeatedly until there is no more work to do. There are specialized (more efficient) mechanisms provided by this class.

Parameters:

changed - Whether analysis of the current element changed any data-flow result.

Returns:

the next node to analyze

See Also:

isSingleSuccessor(org.jikesrvm.compilers.opt.util.SortedGraphNode, org.jikesrvm.compilers.opt.util.SortedGraphNode), isSinglePredecessor(org.jikesrvm.compilers.opt.util.SortedGraphNode, org.jikesrvm.compilers.opt.util.SortedGraphNode)

isSingleSuccessor

public boolean isSingleSuccessor(SortedGraphNode currentNode,
                                 SortedGraphNode nextNode)

This method checks to see if the second parameter has a single predecessor, which is the first parameter. If this condition is true, data flow analyses can reuse their results from the previous iteration rather than perform a meet operation (See LiveAnalysis.java for an example.)

Parameters:

currentNode - the possibly unique predecessor

nextNode - the node of interest

Returns:

if first parameter is the only predecessor of the 2nd parameter

isSinglePredecessor

public boolean isSinglePredecessor(SortedGraphNode currentNode,
                                   SortedGraphNode nextNode)

This method checks to see if the second parameter has a single successor, which is the first parameter. If this condition is true, data flow analyses can reuse their results from the previous iteration rather than perform a meet operation (See LiveAnalysis.java for an example.)

Parameters:

currentNode - the possibly unique predecessor

nextNode - the node of interest

Returns:

if first parameter is the only successor of the 2nd parameter

advanceBarrier

private void advanceBarrier()

This method keeps track of nodes in the graph that are known to not have been visited yet even once. Advance the barrier, if needed