org.jikesrvm.compilers.opt.controlflow

Class AnnotatedLSTNode

java.lang.Object

org.jikesrvm.compilers.opt.util.SpaceEffGraphNode

org.jikesrvm.compilers.opt.controlflow.LSTNode

org.jikesrvm.compilers.opt.controlflow.AnnotatedLSTNode

All Implemented Interfaces:

GraphNode

public final class AnnotatedLSTNode
extends LSTNode

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

• Whether this is a countable, affine or non-regular loop
• The registers being used to hold the loop iterator
• The initial loop iterator value
• The terminal loop iterator value
• The instruction that modifies the iterator
• The phi instruction that merges the redefined iterator with its original value
• The condition used to test for loop termination
• The stride operand

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:

• More complex iterator instructions (sequences rather than single instructions)
• Handle longs, floats and doubles as loop iterators
• Consideration of more loop structures

See Also:

LSTNode

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(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

Fields

Modifier and Type	Field and Description
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

Constructor Summary

Constructors

Constructor and Description
AnnotatedLSTNode(IR ir, LSTNode node) Constructor

Method Summary

Modifier and Type	Method and Description
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)
static Instruction	definingInstruction(Operand op) Find the instruction that defines an operand.
void	dump() Dumps 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) Converts 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()
boolean	isMonotonicDecreasing()
boolean	isMonotonicIncreasing()
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, hasIn, hasOneIn, hasOneIn, hasOneOut, hasOneOut, hasOut, hasZeroIn, hasZeroOut, inEdges, inNodes, insertOut, insertOut, isLoopHeader, onStack, outEdges, outNodes, pointsIn, pointsOut, printExtended, printInEdges, printInNodes, printOutEdges, printOutNodes, remove, removeIn, removeIn, removeOut, removeOut, replaceInEdge, replaceOut, setDfsVisited, setDfsVisitedOnStack, setIndex, setLoopHeader, setNumber, setOnStack, 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?

Parameters:

op - an operand

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

Returns:

whether the loop iterator is monotonic

getMonotonicStrideValue

public int getMonotonicStrideValue()

Return the stride value for monotonic loops

Returns:

the constant stride value

isMonotonicIncreasing

public boolean isMonotonicIncreasing()

Returns:

whether the loop iterator is a monotonic increasing value

isMonotonicDecreasing

public boolean isMonotonicDecreasing()

Returns:

whether the loop iterator is a monotonic decreasing value

contains

public boolean contains(BasicBlock block)

Parameters:

block - the block to chck for

Returns:

true if the basic block appears in the loop

toString

public String toString()

Converts the annotated loop to a concise string

Overrides:

toString in class LSTNode

dump

public void dump()

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

Converts instruction to String in of AnnotatedLSTNode format.

Parameters:

ir - Containing IR

instr - The instruction to dump

Returns:

the converted string

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

Returns:

a (possibly new) operand

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.

Parameters:

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

Returns:

If the operand is a register, return the instruction that defines it. Else return the operand's instruction.

isInLoop

public boolean isInLoop(BasicBlock block)

Is the a particular block in this loop?

Parameters:

block - the block to check for

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 - if the loop was not regular

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 - if the loop was not regular

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 - if the loop was not regular

processExit

private void processExit()
                  throws AnnotatedLSTNode.NonRegularLoopException

Process the loop exit basic block.

Throws:

AnnotatedLSTNode.NonRegularLoopException - if the loop was not regular

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 - if the loop was not regular

getCarriedLoopIterator

public Operand getCarriedLoopIterator()

Get the carried loop iterator

Returns:

carried loop iterator