scale.score.chords
Class SequentialChord

java.lang.Object
  scale.common.Root
      scale.score.Note
          scale.score.chords.Chord
              scale.score.chords.SequentialChord

All Implemented Interfaces:

AnnotationInterface, DisplayNode

Direct Known Subclasses:

BranchChord, EndChord, ExprChord, LoopExitChord, LoopHeaderChord, LoopInitChord, LoopPreHeaderChord, LoopTailChord, MarkerChord, NullChord

public abstract class SequentialChord
extends Chord

This class is a base class for any node in the CFG which does not alter control flow.

$Id: SequentialChord.java,v 1.47 2007-10-17 13:39:59 burrill Exp $

Copyright 2008 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

All superclasses of this class have only one out-going CFG edge.

Field Summary

Fields inherited from class scale.score.chords.Chord

lineNumber

Constructor Summary

SequentialChord()
Construct a new Chord with no out-going CFG edge.

SequentialChord(Chord next)
Construct a new Chord with the indicated out-going CFG edge.

Method Summary

void	changeOutCfgEdge(Chord oldEdge, Chord newEdge) Change the out-going CFG edge indicated by the position to the new edge.
void	clearEdge(int edge) Clear the marker associated with the specified out-going CFG edge.
void	clearEdgeMarkers() Clear all the markers.
void	deleteInDataEdges() Remove all the in-coming adat edges.
void	deleteOutCfgEdges() Set the out-going CFG edge to null.
boolean	edgeMarked(int edge) Return the marker associated with the specified out-going CFG edge.
int	executionCostEstimate() Return a relative cost estimate for executing the expression.
Vector<Declaration>	getDeclList() Return a vector of all declarations referenced in this CFG node or null.
Vector<Expr>	getExprList() Return a vector of all Expr instances in this CFG node or null.
Vector<LoadExpr>	getLoadExprList() Return a vector of all {#link scale.score.expr.LoadExpr LoadExpr} instances in this CFG node or null.
Chord	getNextChord() Return the CFG out-going edge.
Chord	getOutCfgEdge(int i) Return the specified out-going CFG edge.
Chord[]	getOutCfgEdgeArray() Use this method when you may be modifying an out-going CFG edge from this Chord while iterating over the out-going edges.
Chord	getTarget() Return the out-going CFG edge (i.e., target of this branch).
int	indexOfOutCfgEdge(Chord to, int skip) This routine is needed because it is possible for more than one out-going edge from a CFG node to go the the same CFG node.
boolean	isLastInBasicBlock() Return true if this is the last Chord in this Basic Block.
boolean	isSequential() Return true if this is a sequential chord.
void	linkSubgraph(HashMap<Chord,Chord> nm) Link a new CFG node that contains old links.
void	linkTo(Chord child) Link child to parent if it's a SequentialChord and not a BranchChord or EndChord.
void	markEdge(int edge) Set the marker associated with the specified out-going CFG edge.
int	numOutCfgEdges() Return the number of out-going CFG edges.
void	pushAllOutCfgEdges(Stack<Chord> wl) Add the successors of this Chord to the stack.
void	pushOutCfgEdges(Stack<Chord> wl) Add the successors of this Chord to the stack if they haven't been visited before.
void	pushOutCfgEdges(Stack<Chord> wl, HashSet<Chord> done) Add the successors of this Chord to the stack if they haven't been visited before.
void	pushSortedOutCfgEdges(Stack<Chord> wl) Add the successors of this Chord to the stack if they haven't been visited, and all their parents have.
void	pushSortedOutCfgEdges(Stack<Chord> wl, HashSet<Chord> finished) Add the successors of this Chord to the stack if they haven't been visited, and all their parents have.
void	removeUseDef() Remove any use - def links, may - use links, etc.
boolean	replaceDecl(Declaration oldDecl, Declaration newDecl) Replace all occurrances of a Declaration with another Declaration.
void	replaceOutCfgEdge(Chord oldChord, Chord newChord) Replace the existing out-going CFG edge with a new edge.
void	setTarget(Chord target) Set the out-going CFG edge of this node (i.e., target of the branch).
void	setTargetUnsafe(Chord target) Set the out-going CFG edge of this node (i.e., target of the branch).

Methods inherited from class scale.score.chords.Chord

addInCfgEdge, changeInDataEdge, changeParentOutCfgEdge, copy, copySourceLine, deadCFGNodes, deletedCFGNodes, deleteInCfgEdge, executionOrder, expungeFromCfg, extractFromCfg, findLoopExit, findPhiChords, firstInBasicBlock, getCall, getDefExpr, getDisplayColorHint, getDisplayLabel, getDisplayShapeHint, getFirstInCfgEdge, getInCfgEdge, getInCfgEdge, getInCfgEdgeArray, getInDataEdge, getInDataEdgeArray, getLabel, getLoopHeader, getLoopHeader, getLoopNumber, getSourceLineNumber, gotoCFGNodes, inBasicBlock, indexOfInCfgEdge, insertAfterOutCfg, insertBeforeInCfg, isAssignChord, isBranch, isExprChord, isFirstInBasicBlock, isLoopExit, isLoopHeader, isLoopPreHeader, isLoopTail, isMarker, isPhiExpr, isSpecial, lastInBasicBlock, loopClean, nextVisit, nthIndexOfInCfgEdge, nullCFGNodes, numInCfgEdges, numInDataEdges, numOfInCfgEdge, parentsFinished, parentsVisited, pushAllInCfgEdges, pushChordWhenReady, pushChordWhenReady, pushInCfgEdges, pushInCfgEdges, pushInDataEdges, recordRefs, removeDeadCode, removeDualExprs, removeFromCfg, removeRefs, reorderInCfgEdgesOfCopy, replaceInCfgEdge, setLabel, setSourceLineNumber, setVisited, toStringSpecial, unlinkChord, visited

Methods inherited from class scale.score.Note

getChord, getEssentialUse, setAnnotationLevel, setReportLevel, toString, validate, visit

Methods inherited from class scale.common.Root

addAnnotation, allAnnotations, allMatchingAnnotations, getAnnotation, getDisplayName, getDisplayString, getNodeCount, getNodeID, hasAnnotation, hasEqualAnnotation, hashCode, removeAnnotation, removeAnnotations, toStringAnnotations, toStringClass, trace, trace, trace

Methods inherited from class java.lang.Object

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

Constructor Detail

SequentialChord

public SequentialChord(Chord next)

Construct a new Chord with the indicated out-going CFG edge.

Parameters:

next - is the out-going CFG edge

SequentialChord

public SequentialChord()

Construct a new Chord with no out-going CFG edge.

See Also:

setTarget(scale.score.chords.Chord)

Method Detail

isSequential

public final boolean isSequential()

Return true if this is a sequential chord.

Overrides:

isSequential in class Chord

deleteOutCfgEdges

public void deleteOutCfgEdges()

Set the out-going CFG edge to null. This method does not maintain the validity of the CFG as the node at the other ends of the edge is not modified.

Specified by:

deleteOutCfgEdges in class Chord

setTarget

public void setTarget(Chord target)

Set the out-going CFG edge of this node (i.e., target of the branch). The old out-going CFG edge, if any, is replaced. The validity of the CFG graph is maintained.

Parameters:

target - is the out-going CFG edge

setTargetUnsafe

public void setTargetUnsafe(Chord target)

Set the out-going CFG edge of this node (i.e., target of the branch). The old out-going CFG edge, if any, is replaced. The validity of the CFG graph is NOT maintained.

Parameters:

target - is the out-going CFG edge

getTarget

public Chord getTarget()

Return the out-going CFG edge (i.e., target of this branch).

linkTo

public void linkTo(Chord child)

Link child to parent if it's a SequentialChord and not a BranchChord or EndChord.

Overrides:

linkTo in class Chord

replaceOutCfgEdge

public final void replaceOutCfgEdge(Chord oldChord,
                                    Chord newChord)

Replace the existing out-going CFG edge with a new edge. No attempt is made to maintain the validity of the CFG graph; that is the responsibility of the caller.

Specified by:

replaceOutCfgEdge in class Chord

Parameters:

oldChord - is the old edge

newChord - is the new edge

getNextChord

public final Chord getNextChord()

Return the CFG out-going edge.

Specified by:

getNextChord in class Chord

isLastInBasicBlock

public boolean isLastInBasicBlock()

Return true if this is the last Chord in this Basic Block.

Specified by:

isLastInBasicBlock in class Chord

See Also:

Chord.lastInBasicBlock(), Chord.isFirstInBasicBlock(), Chord.firstInBasicBlock()

numOutCfgEdges

public final int numOutCfgEdges()

Return the number of out-going CFG edges.

Specified by:

numOutCfgEdges in class Chord

getOutCfgEdge

public final Chord getOutCfgEdge(int i)

Return the specified out-going CFG edge.

Specified by:

getOutCfgEdge in class Chord

getOutCfgEdgeArray

public final Chord[] getOutCfgEdgeArray()

Use this method when you may be modifying an out-going CFG edge from this Chord while iterating over the out-going edges.

Specified by:

getOutCfgEdgeArray in class Chord

Returns:

an array of all of the out-going CFG edges

indexOfOutCfgEdge

public final int indexOfOutCfgEdge(Chord to,
                                   int skip)

This routine is needed because it is possible for more than one out-going edge from a CFG node to go the the same CFG node. This method should be over-ridden by the derived classes for speed.

Specified by:

indexOfOutCfgEdge in class Chord

Parameters:

to - is the target CFG node

skip - ispecifies how many occurrances of to to skip

Returns:

the index into the outgoing edges of this node that matches the specified in-coming edge of the target node.

pushAllOutCfgEdges

public final void pushAllOutCfgEdges(Stack<Chord> wl)

Add the successors of this Chord to the stack.

Specified by:

pushAllOutCfgEdges in class Chord

pushOutCfgEdges

public final void pushOutCfgEdges(Stack<Chord> wl)

Add the successors of this Chord to the stack if they haven't been visited before.

Specified by:

pushOutCfgEdges in class Chord

See Also:

Chord.nextVisit(), Chord.setVisited(), Chord.visited()

pushOutCfgEdges

public final void pushOutCfgEdges(Stack<Chord> wl,
                                  HashSet<Chord> done)

Add the successors of this Chord to the stack if they haven't been visited before.

Specified by:

pushOutCfgEdges in class Chord

Parameters:

done - is the set of visited CFG nodes

pushSortedOutCfgEdges

public void pushSortedOutCfgEdges(Stack<Chord> wl)

Add the successors of this Chord to the stack if they haven't been visited, and all their parents have. Traversing the graph in this fashion yields a topological sort of the graph (with loop back edges removed).

Specified by:

pushSortedOutCfgEdges in class Chord

pushSortedOutCfgEdges

public void pushSortedOutCfgEdges(Stack<Chord> wl,
                                  HashSet<Chord> finished)

Add the successors of this Chord to the stack if they haven't been visited, and all their parents have. Traversing the graph in this fashion yields a topological sort of the graph (with loop back edges removed).

Specified by:

pushSortedOutCfgEdges in class Chord

Parameters:

finished - is the set of finished nodes.

clearEdgeMarkers

public final void clearEdgeMarkers()

Clear all the markers. Each marker is associated with one out-going CFG edge..

Specified by:

clearEdgeMarkers in class Chord

edgeMarked

public final boolean edgeMarked(int edge)

Return the marker associated with the specified out-going CFG edge.

Specified by:

edgeMarked in class Chord

Parameters:

edge - specifies the edge associated with the marker

Returns:

true is the specified edge is marked

markEdge

public final void markEdge(int edge)

Set the marker associated with the specified out-going CFG edge.

Specified by:

markEdge in class Chord

Parameters:

edge - specifies the edge associated with the marker

clearEdge

public final void clearEdge(int edge)

Clear the marker associated with the specified out-going CFG edge.

Specified by:

clearEdge in class Chord

Parameters:

edge - specifies the edge associated with the marker

deleteInDataEdges

public void deleteInDataEdges()

Remove all the in-coming adat edges.

Specified by:

deleteInDataEdges in class Chord

changeOutCfgEdge

public void changeOutCfgEdge(Chord oldEdge,
                             Chord newEdge)

Change the out-going CFG edge indicated by the position to the new edge. The validity of the CFG graph is maintained.

Specified by:

changeOutCfgEdge in class Chord

Parameters:

oldEdge - the out-going CFG edge to be changed

newEdge - the new out-going CFG edge

getDeclList

public Vector<Declaration> getDeclList()

Return a vector of all declarations referenced in this CFG node or null.

Specified by:

getDeclList in class Chord

getLoadExprList

public Vector<LoadExpr> getLoadExprList()

Return a vector of all {#link scale.score.expr.LoadExpr LoadExpr} instances in this CFG node or null.

Specified by:

getLoadExprList in class Chord

getExprList

public Vector<Expr> getExprList()

Return a vector of all Expr instances in this CFG node or null.

Specified by:

getExprList in class Chord

replaceDecl

public boolean replaceDecl(Declaration oldDecl,
                           Declaration newDecl)

Replace all occurrances of a Declaration with another Declaration. Return true if a replace occurred.

Specified by:

replaceDecl in class Chord

removeUseDef

public void removeUseDef()

Remove any use - def links, may - use links, etc.

Specified by:

removeUseDef in class Chord

linkSubgraph

public void linkSubgraph(HashMap<Chord,Chord> nm)

Link a new CFG node that contains old links. When a CFG node is copied, the copy has the same links as the original node. This method updates those links.

Specified by:

linkSubgraph in class Chord

Parameters:

nm - is a map from the old nodes to the new nodes.

See Also:

Scribble.linkSubgraph(scale.common.Vector, scale.common.HashMap, scale.common.Vector)

executionCostEstimate

public int executionCostEstimate()

Return a relative cost estimate for executing the expression.

Specified by:

executionCostEstimate in class Note