Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.jikesrvm.compilers.opt.controlflow
Class LSTGraph

java.lang.Object
  extended by org.jikesrvm.compilers.opt.util.SpaceEffGraph
      extended by 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
private static boolean DEBUG
           
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
private LSTGraph(IR ir)
          Constructor, it creates the LST graph
protected LSTGraph(LSTGraph graph)
          Copying constructor
 
Method Summary
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)
          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)
          Is the edge from source to target an exit from the loop containing source?
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

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)
Is the edge from source to target an exit from the loop containing source?

Parameters:
source - the basic block that is the source of the edge
target - the basic block that is the target of the edge

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

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
Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD