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 AnnotatedLSTNode

java.lang.Object
  extended by org.jikesrvm.compilers.opt.util.SpaceEffGraphNode
      extended by org.jikesrvm.compilers.opt.controlflow.LSTNode
          extended by org.jikesrvm.compilers.opt.controlflow.AnnotatedLSTNode
All Implemented Interfaces:
GraphElement, GraphNode
public final class AnnotatedLSTNode
extends LSTNode

A node in the LST (Loop Structure Tree) with added information on:

The information is only held on regular loops. The regular loop structure is: predecessor: initialLoopIterator = ...; header: phiLoopIterator = phi (initialLoopIterator, carriedLoopIterator) ...body1... carriedLoopIterator = phiLoopIterator iteratorInstr.opcode stride; ...body2... exit: if carriedLoopIterator condition terminalIteratorValue goto header successor: While loops (and implicitly for loops) aren't handled as they can be transformed to this form by CFGTransformations. TODO:

See Also:
LSTNode

Nested Class Summary
(package private) static class AnnotatedLSTNode.BBEnum
          This class implements an enumeration of BasicBlocks.
private static class AnnotatedLSTNode.NonRegularLoopException
          Exception thrown when a non-regular loop is encountered
 
Nested classes/interfaces inherited from class org.jikesrvm.compilers.opt.controlflow.LSTNode
LSTNode.Edge
 
Nested classes/interfaces inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraphNode
SpaceEffGraphNode.GraphEdgeEnumeration<T extends GraphEdge>, SpaceEffGraphNode.OutEdgeEnumeration
 
Field Summary
private  Operand carriedLoopIterator
          The iterator that is used to loop within the exit block
 ConditionOperand condition
          The condition that is used to check for the end of loop
private static boolean DEBUG
          Flag to optionally print verbose debugging messages
 BasicBlock exit
          The in loop block that either loops or leaves the loop
private  Instruction ifCmpInstr
          The if instruction within the exit block
 Operand initialIteratorValue
          The the initial iterator that comes into the phi node in the header
private  IR ir
          A pointer to the governing IR
private  Instruction iteratorInstr
          The instruction that modifies the iterator
private  Operand phiLoopIterator
          The the phi iterator that gets modified by the stride to produce the carried iterator
 BasicBlock predecessor
          The out of loop block before the header
 Operand strideValue
          The stride operand to the iterator instruction
 BasicBlock successor
          The out of loop block following the exit block
 Operand terminalIteratorValue
          The value that ends the loop
 
Fields inherited from class org.jikesrvm.compilers.opt.controlflow.LSTNode
depth, header, loop, loopExits, loopMultiplier
 
Fields inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraphNode
_inEdgeEnd, _inEdgeStart, _outEdgeEnd, _outEdgeStart, info, next, nextSorted, prev, scratch, scratchObject
 
Constructor Summary
AnnotatedLSTNode(IR ir, LSTNode node)
          Constructor
 
Method Summary
private  void checkInEdgesAreInLoop(BasicBlock block)
          Check the edges into a block are from within the loop
private  void checkOutEdgesAreInLoop(BasicBlock block)
          Check the edges out of a block are within the loop
 boolean contains(BasicBlock block)
          Does this basic block appear in the loop?
static Instruction definingInstruction(Operand op)
          Find the instruction that defines an operand.
 void dump()
          Dump a human readable description of the loop
(package private)  void dumpBlock(BasicBlock block)
          Dump a human readable description of a basic block within the loop
(package private) static void dumpInstruction(IR ir, Instruction instr)
          Dump a human readable description of an instruction within a basic block within the loop
static Operand follow(Operand use)
          Follow the operand's definition filtering out moves This code is taken and modified from an old LoopUnrolling
 Operand generateLoopInvariantOperand(BasicBlock block, Operand op)
          Loop invariants may not be accessible before a loop, so generate the instructions so they are
 Enumeration<BasicBlock> getBasicBlocks()
          Return an enumeration of basic blocks corresponding to a depth first traversal of the blocks in the loops graphs
private  AnnotatedLSTNode.BBEnum getBasicBlocks(BasicBlock block, AnnotatedLSTNode.BBEnum bbs, BitVector blocksLeftToVisit)
          Return an enumeration of basic blocks corresponding to a depth first traversal of the blocks in the loops graphs
 Operand getCarriedLoopIterator()
          Get the carried loop iterator
 int getFixedDistanceFromPhiIterator(Operand op)
          Get fixed distance from the phi iterator
 int getMonotonicStrideValue()
          Return the stride value for monotonic loops
(package private) static String instructionToString(IR ir, Instruction instr)
          Convert instruction to String in of AnnotatedLSTNode format
 boolean isAffineLoop()
          Is this an affine loop of the form: predecessor: initialLoopIterator = ...; header: phiLoopIterator = phi (initialLoopIterator, carriedLoopIterator) ...body1...
 boolean isCarriedLoopIterator(Operand op)
          Is this operand related to the carried iterator of this loop?
(package private) static boolean isConstant(Operand op)
          Test whether the operand is constant
 boolean isCountableLoop()
          Is this a countable loop of the form: predecessor: initialLoopIterator = ConstantInitialValue; header: phiLoopIterator = phi (initialLoopIterator, carriedLoopIterator) ...body1...
(package private)  boolean isFixedDistanceFromPhiIterator(Operand op)
          Is this operand a fixed distance from the phi iterator?
 boolean isInLoop(BasicBlock block)
          Is the a particular block in this loop?
 boolean isInvariant(Operand op)
          Is this value modified by the loop?
private static boolean isLoopInvariant(Operand op, BitVector loop, BasicBlock header)
          Test whether operand value will be invariant in a loop by tracing back earlier definitions.
 boolean isMonotonic()
          Is the loop iterator monotonic?
 boolean isMonotonicDecreasing()
          Is the loop iterator a monotonic decreasing value
 boolean isMonotonicIncreasing()
          Is the loop iterator a monotonic increasing value
 boolean isNonRegularLoop()
          Is this loop a non-regular loop?
 boolean isPhiLoopIterator(Operand op)
          Is this operand related to the phi iterator of this loop?
 boolean isRelatedToIterator(Operand op)
          Is this operand related to the iterator of this loop?
private  void perform()
          Convert node into annotated format
private  void processExit()
          Process the loop exit basic block
private  void processHeader()
          Process the loop header basic block
private  void processLoopBlock(BasicBlock block)
          Process a regular block within the loop
 String toString()
          Converts the annotated loop to a concise string
 
Methods inherited from class org.jikesrvm.compilers.opt.controlflow.LSTNode
addLoopExit, getChildren, getHeader, getLoop, getParent, initializeLoopExits
 
Methods inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraphNode
_sortDFS, _sortRevTop, _sortTop, append, appendInEdge, appendOutEdge, clearDfsVisited, clearFlags, clearInFlags, clearLoopHeader, clearOnStack, clearOutFlags, clearTopVisited, deleteIn, deleteOut, deleteOut, deleteOut, dfsVisited, findOutEdgeTo, firstInEdge, firstInNode, firstOutEdge, firstOutNode, flagsOn, getIndex, getNext, getNumber, getNumberOfIn, getNumberOfOut, getPrev, getScratch, hasIn, hasOneIn, hasOneIn, hasOneOut, hasOneOut, hasOut, hasZeroIn, hasZeroOut, inEdges, inNodes, insertOut, insertOut, isLoopHeader, markDFN, markSCC, onStack, outEdges, outNodes, pointsIn, pointsOut, printExtended, printInEdges, printInNodes, printOutEdges, printOutNodes, remove, removeIn, removeIn, removeOut, removeOut, replaceInEdge, replaceOut, setDfsVisited, setDfsVisitedOnStack, setIndex, setLoopHeader, setNumber, setOnStack, setScratch, setTopVisited, sortDFS, sortRevTop, sortTop, topVisited
 
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
Flag to optionally print verbose debugging messages

See Also:
Constant Field Values

ir

private final IR ir
A pointer to the governing IR

predecessor

public BasicBlock predecessor
The out of loop block before the header

exit

public BasicBlock exit
The in loop block that either loops or leaves the loop

successor

public BasicBlock successor
The out of loop block following the exit block

ifCmpInstr

private Instruction ifCmpInstr
The if instruction within the exit block

iteratorInstr

private Instruction iteratorInstr
The instruction that modifies the iterator

initialIteratorValue

public Operand initialIteratorValue
The the initial iterator that comes into the phi node in the header

carriedLoopIterator

private Operand carriedLoopIterator
The iterator that is used to loop within the exit block

phiLoopIterator

private Operand phiLoopIterator
The the phi iterator that gets modified by the stride to produce the carried iterator

terminalIteratorValue

public Operand terminalIteratorValue
The value that ends the loop

condition

public ConditionOperand condition
The condition that is used to check for the end of loop

strideValue

public Operand strideValue
The stride operand to the iterator instruction

Constructor Detail

AnnotatedLSTNode

public AnnotatedLSTNode(IR ir,
                        LSTNode node)
Constructor

Parameters:
ir - The containing IR
node - The node that's being annotated
Method Detail

isCountableLoop

public boolean isCountableLoop()
Is this a countable loop of the form: predecessor: initialLoopIterator = ConstantInitialValue; header: phiLoopIterator = phi (initialLoopIterator, carriedLoopIterator) ...body1... carriedLoopIterator = phiLoopIterator (+|-) ConstantStride; ...body2... exit: if carriedLoopIterator condition ConstantTerminalIteratorValue goto header successor: ie. lots of constant fields so we can calculate the number of loop iterations (handy for pre-scheduling).

Returns:
Whether this a countable loop or not

isAffineLoop

public boolean isAffineLoop()
Is this an affine loop of the form: predecessor: initialLoopIterator = ...; header: phiLoopIterator = phi (initialLoopIterator, carriedLoopIterator) ...body1... carriedLoopIterator = phiLoopIterator (+|-) invariantStride; ...body2... exit: if carriedLoopIterator condition invariantTerminalIteratorValue goto header successor: ie. lots of constant fields so we can calculate the number of loop iterations (handy for pre-scheduling).

Returns:
Whether this an affine loop or not

isNonRegularLoop

public boolean isNonRegularLoop()
Is this loop a non-regular loop?

Returns:
Whether this is a non-regular loop

isInvariant

public boolean isInvariant(Operand op)
Is this value modified by the loop?

Returns:
whether the value is modified

isRelatedToIterator

public boolean isRelatedToIterator(Operand op)
Is this operand related to the iterator of this loop?

Parameters:
op - Operand to test
Returns:
whether related to iterator (initial, phi or carried)

isPhiLoopIterator

public boolean isPhiLoopIterator(Operand op)
Is this operand related to the phi iterator of this loop?

Parameters:
op - Operand to test
Returns:
whether related to iterator (phi)

isCarriedLoopIterator

public boolean isCarriedLoopIterator(Operand op)
Is this operand related to the carried iterator of this loop?

Parameters:
op - Operand to test
Returns:
whether related to iterator (carried)

isMonotonic

public boolean isMonotonic()
Is the loop iterator monotonic?

getMonotonicStrideValue

public int getMonotonicStrideValue()
Return the stride value for monotonic loops

Returns:
the constant stride value

isMonotonicIncreasing

public boolean isMonotonicIncreasing()
Is the loop iterator a monotonic increasing value

isMonotonicDecreasing

public boolean isMonotonicDecreasing()
Is the loop iterator a monotonic decreasing value

contains

public boolean contains(BasicBlock block)
Does this basic block appear in the loop?

toString

public String toString()
Converts the annotated loop to a concise string

Overrides:
toString in class LSTNode

dump

public void dump()
Dump a human readable description of the loop

dumpBlock

void dumpBlock(BasicBlock block)
Dump a human readable description of a basic block within the loop

Parameters:
block - The basic block to dump

dumpInstruction

static void dumpInstruction(IR ir,
                            Instruction instr)
Dump a human readable description of an instruction within a basic block within the loop

Parameters:
ir - Containing IR
instr - The instruction to dump

instructionToString

static String instructionToString(IR ir,
                                  Instruction instr)
Convert instruction to String in of AnnotatedLSTNode format

Parameters:
ir - Containing IR
instr - The instruction to dump

isConstant

static boolean isConstant(Operand op)
Test whether the operand is constant

Parameters:
op - Operand to determine whether it's constant
Returns:
Is the operand constant

isFixedDistanceFromPhiIterator

boolean isFixedDistanceFromPhiIterator(Operand op)
Is this operand a fixed distance from the phi iterator?

Parameters:
op - the operand to test
Returns:
whether or not it is a fixed distance

getFixedDistanceFromPhiIterator

public int getFixedDistanceFromPhiIterator(Operand op)
Get fixed distance from the phi iterator

Parameters:
op - the operand to test
Returns:
the fixed distance

isLoopInvariant

private static boolean isLoopInvariant(Operand op,
                                       BitVector loop,
                                       BasicBlock header)
Test whether operand value will be invariant in a loop by tracing back earlier definitions. There is similar code in LoopUnrolling.

Parameters:
op - Operand to determine whether it's invariant
loop - Loop in which we wish to know the invariance of the operand
header - The loop header for determining if PEIs are invariant
Returns:
Whether the operand is invariant or not

generateLoopInvariantOperand

public Operand generateLoopInvariantOperand(BasicBlock block,
                                            Operand op)
Loop invariants may not be accessible before a loop, so generate the instructions so they are

Parameters:
block - to generate instructions into
op - the operand we hope to use before the loop

follow

public static Operand follow(Operand use)
Follow the operand's definition filtering out moves This code is taken and modified from an old LoopUnrolling

Parameters:
use - Operand to follow
Returns:
the first defintion of the instruction which isn't a move

definingInstruction

public static Instruction definingInstruction(Operand op)
Find the instruction that defines an operand. If the operand is a register, return the instruction that defines it, else return the operands instruction

Parameters:
op - The operand we're searching for the definition of

isInLoop

public boolean isInLoop(BasicBlock block)
Is the a particular block in this loop?

Returns:
true iff block is in the loop

getBasicBlocks

private AnnotatedLSTNode.BBEnum getBasicBlocks(BasicBlock block,
                                               AnnotatedLSTNode.BBEnum bbs,
                                               BitVector blocksLeftToVisit)
Return an enumeration of basic blocks corresponding to a depth first traversal of the blocks in the loops graphs

Parameters:
block - block to visit
bbs - enumeration so far
blocksLeftToVisit - blocks left to visit
Returns:
Blocks in loop with header first and exit last

getBasicBlocks

public Enumeration<BasicBlock> getBasicBlocks()
Return an enumeration of basic blocks corresponding to a depth first traversal of the blocks in the loops graphs

Returns:
Blocks in loop with header first and exit last

checkOutEdgesAreInLoop

private void checkOutEdgesAreInLoop(BasicBlock block)
                             throws AnnotatedLSTNode.NonRegularLoopException
Check the edges out of a block are within the loop

Parameters:
block - to check
Throws:
AnnotatedLSTNode.NonRegularLoopException

checkInEdgesAreInLoop

private void checkInEdgesAreInLoop(BasicBlock block)
                            throws AnnotatedLSTNode.NonRegularLoopException
Check the edges into a block are from within the loop

Parameters:
block - to check
Throws:
AnnotatedLSTNode.NonRegularLoopException

perform

private void perform()
              throws OptimizingCompilerException
Convert node into annotated format

Throws:
OptimizingCompilerException

processHeader

private void processHeader()
                    throws AnnotatedLSTNode.NonRegularLoopException
Process the loop header basic block

Throws:
AnnotatedLSTNode.NonRegularLoopException

processExit

private void processExit()
                  throws AnnotatedLSTNode.NonRegularLoopException
Process the loop exit basic block

Throws:
AnnotatedLSTNode.NonRegularLoopException

processLoopBlock

private void processLoopBlock(BasicBlock block)
                       throws AnnotatedLSTNode.NonRegularLoopException
Process a regular block within the loop

Parameters:
block - The basic block to process
Throws:
AnnotatedLSTNode.NonRegularLoopException

getCarriedLoopIterator

public Operand getCarriedLoopIterator()
Get the carried loop iterator

Returns:
carried loop iterator
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