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);
  }

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

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

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