org.jikesrvm.compilers.opt.controlflow

Class LSTGraph

java.lang.Object

org.jikesrvm.compilers.opt.util.SpaceEffGraph

org.jikesrvm.compilers.opt.controlflow.LSTGraph

All Implemented Interfaces:

Graph, TopSortInterface

Direct Known Subclasses:

AnnotatedLSTGraph

public class LSTGraph
extends SpaceEffGraph

Identify natural loops and builds the LST (Loop Structure Tree)

Note: throws an exception if an irreducible loop is found (which I believe could only happen in Java from modified bytecode, because Java source code is structured enough to prevent irreducible loops.)

See Also:

DominatorsPhase

Field Summary

Fields

Modifier and Type	Field and Description
private static boolean	DEBUG
private IR	ir
private HashMap<BasicBlock,LSTNode>	loopMap Map of bb to LSTNode of innermost loop containing bb
protected LSTNode	rootNode

Fields inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraph

_firstNode, _lastNode, backwardTopSorted, forwardTopSorted, numberOfNodes

Constructor Summary

Constructors

Modifier	Constructor and Description
private	LSTGraph(IR ir) Constructor, it creates the LST graph
protected	LSTGraph(LSTGraph graph) Copying constructor

Method Summary

Modifier and Type	Method and Description
private void	clearBackEdges(SpaceEffGraphNode bb) Clears the back edges for the basic block passed
private String	dumpIt(LSTNode n)
private void	findBackEdges(BasicBlock bb, int numBlocks, Map<SpaceEffGraphNode,Integer> dfnMap) This routine performs a non-recursive depth-first search starting at the block passed looking for back edges.
private void	findNaturalLoop(SpaceEffGraphEdge edge, BitVector loop) This routine implements part of the algorithm to compute natural loops as defined in Muchnick p 192.
LSTNode	getLoop(BasicBlock b)
int	getLoopNestDepth(BasicBlock bb)
LSTNode	getRoot() Return the root node of the tree
boolean	inInnermostLoop(BasicBlock bb) Is a given basic block in an innermost loop?
boolean	isLoopExit(BasicBlock source, BasicBlock target)
static void	perform(IR ir) The main entry point
private void	setDepth(IR ir, LSTNode node, int depth)
String	toString() Return a string representation of this graph.

Methods inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraph

addGraphEdge, addGraphEdge, addGraphNode, addRootNode, addTopSortNode, allocateNodeNumber, buildRevTopSort, buildTopSort, clearDFS, compactNodeNumbering, enumerateNodes, firstNode, initTopSort, isTopSorted, lastNode, numberOfNodes, printDepthFirst, removeGraphNode, resetTopSorted, rootNodes, setFirstNode, setLastNode, setNumberOfNodes, setTopSorted, startNode, topSort, topSortOrder

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

private static final boolean DEBUG

See Also:

Constant Field Values

rootNode

protected LSTNode rootNode

loopMap

private final HashMap<BasicBlock,LSTNode> loopMap

Map of bb to LSTNode of innermost loop containing bb

ir

private IR ir

Constructor Detail

LSTGraph

protected LSTGraph(LSTGraph graph)

Copying constructor

Parameters:

graph - to copy

LSTGraph

private LSTGraph(IR ir)

Constructor, it creates the LST graph

Parameters:

ir - the IR

Method Detail

perform

public static void perform(IR ir)

The main entry point

Parameters:

ir - the IR to process

getLoopNestDepth

public int getLoopNestDepth(BasicBlock bb)

Parameters:

bb - the basic block

Returns:

the loop nesting depth or 0, if not in loop

inInnermostLoop

public boolean inInnermostLoop(BasicBlock bb)

Is a given basic block in an innermost loop?

Parameters:

bb - the basic block

Returns:

whether the block is in an innermost loop

isLoopExit

public boolean isLoopExit(BasicBlock source,
                          BasicBlock target)

getLoop

public LSTNode getLoop(BasicBlock b)

getRoot

public LSTNode getRoot()

Return the root node of the tree

Returns:

the root node of the loop structure tree

toString

public String toString()

Description copied from class: SpaceEffGraph

Return a string representation of this graph.

Overrides:

toString in class SpaceEffGraph

Returns:

a string representation of the graph

dumpIt

private String dumpIt(LSTNode n)

setDepth

private void setDepth(IR ir,
                      LSTNode node,
                      int depth)

findBackEdges

private void findBackEdges(BasicBlock bb,
                           int numBlocks,
                           Map<SpaceEffGraphNode,Integer> dfnMap)

This routine performs a non-recursive depth-first search starting at the block passed looking for back edges. It uses dominator information to determine back edges.

Parameters:

bb - The basic block to process

numBlocks - The number of basic blocks

dfnMap - numbering from the depth first traversal

clearBackEdges

private void clearBackEdges(SpaceEffGraphNode bb)

Clears the back edges for the basic block passed

Parameters:

bb - the basic block

findNaturalLoop

private void findNaturalLoop(SpaceEffGraphEdge edge,
                             BitVector loop)

This routine implements part of the algorithm to compute natural loops as defined in Muchnick p 192. See caller for more details.

Parameters:

edge - the edge to process

loop - bit vector to hold the results of the algorithm