scale.score.chords
Class Chord

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

All Implemented Interfaces:

AnnotationInterface, DisplayNode

Direct Known Subclasses:

DecisionChord, SequentialChord

public abstract class Chord
extends Note

This class represents nodes in a CFG.

$Id: Chord.java,v 1.137 2007-10-04 19:58:22 burrill Exp $

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

The Chord class has derived classes which are dependent on the number of out-going CFG edges. Chord nodes have no out-going data edges. This class handles the in-coming CFG edges. The derived classes must handle the out-going CFG edges.

Field Summary

protected int

lineNumber The source line number.

Constructor Summary

protected

Chord()

Method Summary

void	addInCfgEdge(Chord node) Add an in-coming CFG edge.
void	changeInDataEdge(Expr oldExpr, Expr newExpr) This method changes an incoming data edge to point to a new expression.
abstract void	changeOutCfgEdge(Chord oldEdge, Chord newEdge) Change the out-going CFG edge indicated by the position to the new edge.
void	changeParentOutCfgEdge(Chord newEdge) Change all my predecessors to point to another CFG node.
abstract void	clearEdge(int edge) Clear the marker associated with the specified out-going CFG edge.
abstract void	clearEdgeMarkers() Clear all the markers.
abstract Chord	copy() Make a copy of this CFG node with the same out-going CFG edges.
void	copySourceLine(Chord from) Copy the source line information.
static int	deadCFGNodes() Return the current number of dead nodes removed because they were not reachable.
static int	deletedCFGNodes() Return the current number of dead nodes removed.
void	deleteInCfgEdge(Chord node) Remove an in-coming CFG edge.
abstract void	deleteInDataEdges() Remove all the in-coming data edges.
abstract void	deleteOutCfgEdges() Remove all the out-going CFG edges.
abstract boolean	edgeMarked(int edge) Return the marker associated with the specified out-going CFG edge.
int	executionOrder(Chord n) Determine the execution ordering of the two CFG nodes.
void	expungeFromCfg() Remove myself from the CFG.
void	extractFromCfg() Remove myself from the CFG but preserve me for future use.
LoopExitChord	findLoopExit(LoopHeaderChord header) Return the LoopExitChord instance, for the specified loop, that is reachable from this CFG node.
Vector<PhiExprChord>	findPhiChords() Return a vector of all of the phi chords in the basic block starting at this node.
Chord	firstInBasicBlock() Return the first CFG node in this basic block.
CallExpr	getCall(boolean ignorePure) Return the call expression or null if none.
abstract Vector<Declaration>	getDeclList() Return a vector of all declarations referenced in this CFG node or null.
Expr	getDefExpr() If this CFG node results in a variable being given a new value, return the Expr instance that specifies the variable.
DColor	getDisplayColorHint() Return a String specifying the color to use for coloring this node in a graphical display.
java.lang.String	getDisplayLabel() Return a String suitable for labeling this node in a graphical display.
DShape	getDisplayShapeHint() Return a String specifying a shape to use when drawing this node in a graphical display.
abstract Vector<Expr>	getExprList() Return a vector of all Expr instances in this CFG node or null.
Chord	getFirstInCfgEdge() Return the predecessor node.
Chord	getInCfgEdge() Return the predecessor node.
Chord	getInCfgEdge(int i) Return the i-th predecessor node.
Chord[]	getInCfgEdgeArray() Use this method when you may be modifying an in-coming CFG edge to this CFG node while iterating over the in-coming edges.
Expr	getInDataEdge(int i) Return the specified in-coming data edge.
Expr[]	getInDataEdgeArray() Use this method when you may be modifying an in-coming data edge to this expression while iterating over the in-coming edges.
int	getLabel() Return the integer associated with a CFG node.
abstract Vector<LoadExpr>	getLoadExprList() Return a vector of all LoadExpr instances in this CFG node or null.
LoopHeaderChord	getLoopHeader() Return the LoopHeaderChord object for the loop that contains this node.
LoopHeaderChord	getLoopHeader(int limit) Return the LoopHeaderChord object for the loop that contains this node.
int	getLoopNumber()
abstract Chord	getNextChord() Return the next CFG node in the CFG.
abstract Chord	getOutCfgEdge(int i) Return the specified out-going CFG edge.
abstract Chord[]	getOutCfgEdgeArray() Use this method when you may be modifying an out-going CFG edge from this CFG node while iterating over the out-going edges.
int	getSourceLineNumber() Return the source line number associated with this node or -1 if not known.
static int	gotoCFGNodes() Return the current number of GotoChord nodes removed.
boolean	inBasicBlock(Chord first) Return true if this CFG node is in the basic block specified by first.
int	indexOfInCfgEdge(Chord in) Return the index of the specified in-coming CFG edge.
abstract int	indexOfOutCfgEdge(Chord to, int skip) This routine is needed because it is possible for more than one out-going CFG edge from a CFG node to go the the same CFG node.
void	insertAfterOutCfg(Chord newChord, Chord outEdge) Insert a new node between me and my out-going CFG edges.
void	insertBeforeInCfg(SequentialChord newChord) Insert a new node before me in the CFG.
boolean	isAssignChord() Return true if this node holds an expression that represents an assignment statement.
boolean	isBranch() Return true if this CFG node may have multiple out-going CFG edges.
boolean	isExprChord() Return true if this is an ExprChord instance.
boolean	isFirstInBasicBlock() Return true if this CFG node is the start of a basic block.
abstract boolean	isLastInBasicBlock() Return true if this is the last CFG node in this basic block.
boolean	isLoopExit() Return true if this CFG node is a LoopExitChord instance.
boolean	isLoopHeader() Return true if this CFG node is a LoopHeaderChord instance.
boolean	isLoopPreHeader() Return true if this CFG node is a LoopPreHeaderChord instance.
boolean	isLoopTail() Return true if this CFG node is a LoopTailChord instance.
boolean	isMarker() Return true if this is a marker CFG node.
boolean	isPhiExpr() Return true if this CFG node is a PhiExprChord instance.
boolean	isSequential() Return true if this is a SequentialChord instance.
boolean	isSpecial() Return true if this is CFG node was added for the convenience of the compiler and does not correspond to actual source code in the user program.
Chord	lastInBasicBlock() Return the last CFG node in this basic block.
abstract 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 instance and not a BranchChord instance or EndChord instance.
void	loopClean() Eliminate associated loop information.
abstract void	markEdge(int edge) Set the marker associated with the specified out-going CFG edge.
static void	nextVisit() Set up for a new CFG traversal - that is, use the next color value.
int	nthIndexOfInCfgEdge(Chord in, int n) Return the index of the nth occurrence of the specified in-coming CFG edge.
static int	nullCFGNodes() Return the current number of null nodes removed.
int	numInCfgEdges() Return the number of in-coming CFG edges.
int	numInDataEdges() Return the number of in-coming data edges.
int	numOfInCfgEdge(Chord in) Return the number of duplicate in-coming CFG edges from the specified node.
abstract int	numOutCfgEdges() Return the number of out-going CFG edges.
boolean	parentsFinished(HashSet<Chord> finished) Return true if all predecessor CFG nodes are in the finished set.
boolean	parentsVisited() Return true if the parents of this CFG node have been visited.
void	pushAllInCfgEdges(Stack<Chord> wl) Add the predecessors of this CFG node to the stack.
abstract void	pushAllOutCfgEdges(Stack<Chord> wl) Add the successors of this CFG node to the stack.
void	pushChordWhenReady(Stack<Chord> wl) Place this CFG node on the stack when all its predecessor nodes have been visited.
int	pushChordWhenReady(Stack<Chord> wl, int label) Place this CFG node on the stack when all its predecessor nodes have been visited.
void	pushInCfgEdges(Stack<Chord> wl) Add the predecessors of this CFG node to the stack if they haven't been visited before.
void	pushInCfgEdges(Stack<Chord> wl, HashSet<Chord> done) Add the predecessors of this CFG node to the stack if they haven't been visited before.
void	pushInDataEdges(Stack<Expr> wl) Push all incoming data edges on the stack.
abstract void	pushOutCfgEdges(Stack<Chord> wl) Add the successors of this CFG node to the stack if they haven't been visited before.
abstract void	pushOutCfgEdges(Stack<Chord> wl, HashSet<Chord> done) Add the successors of this CFG node to the stack if they haven't been visited before.
abstract void	pushSortedOutCfgEdges(Stack<Chord> wl) Add the successors of this CFG node to the stack if they haven't been visited, and all their parents have.
abstract void	pushSortedOutCfgEdges(Stack<Chord> wl, HashSet<Chord> finished) Add the successors of this CFG node to the stack if they haven't been visited, and all their parents have.
void	recordRefs(References refs) Record any variable references in this CFG node in the table of references.
static void	removeDeadCode(Stack<Chord> chords) Remove any CFG nodes that do not have an incoming CFG edge and any un-needed nodes from the CFG.
boolean	removeDualExprs() Remove all DualExpr instances from the CFG.
void	removeFromCfg() Remove myself from the CFG.
void	removeRefs(References refs) Remove any variable references in this CFG node from the table of references.
abstract void	removeUseDef() Remove any use - def links, may - use links, etc.
void	reorderInCfgEdgesOfCopy(HashMap<Chord,Chord> nm) Reorder the incoming CFG edges of a new CFG node to match the order of the in-coming edges of the this CFG node.
abstract boolean	replaceDecl(Declaration oldDecl, Declaration newDecl) Replace all occurrances of a Declaration with another declaration.
void	replaceInCfgEdge(Chord oldChord, Chord newChord) Replace the existing in-coming CFG edge with a new edge.
abstract void	replaceOutCfgEdge(Chord oldChord, Chord newChord) Replace the existing out-going CFG edge with a new edge.
void	setLabel(int label) Associate an integer value with a CFG node.
void	setSourceLineNumber(int lineNumber) Set the source line number associated with this node.
void	setVisited() Associate the current color value with a CFG node.
java.lang.String	toStringSpecial() Return a String containing additional information about this CFG node.
void	unlinkChord() Break any un-needed links from a CFG node that is being deleted.
boolean	visited() Return true if this CFG node has been visited during the current visit (i.e., is the current color).

Methods inherited from class scale.score.Note

executionCostEstimate, 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

Field Detail

lineNumber

protected int lineNumber

The source line number.

Constructor Detail

Chord

protected Chord()

Method Detail

deletedCFGNodes

public static int deletedCFGNodes()

Return the current number of dead nodes removed.

deadCFGNodes

public static int deadCFGNodes()

Return the current number of dead nodes removed because they were not reachable.

nullCFGNodes

public static int nullCFGNodes()

Return the current number of null nodes removed.

gotoCFGNodes

public static int gotoCFGNodes()

Return the current number of GotoChord nodes removed.

nextVisit

public static void nextVisit()

Set up for a new CFG traversal - that is, use the next color value. This color is used to mark CFG nodes in CFG spanning algorithms.

See Also:

setVisited(), visited(), nextVisit(), pushOutCfgEdges(scale.common.Stack), pushInCfgEdges(scale.common.Stack)

setLabel

public final void setLabel(int label)

Associate an integer value with a CFG node. The label is for the use of various algorithms so that they can label a CFG node with an integer value. The Domination class uses it in computing dominators.

getLabel

public final int getLabel()

Return the integer associated with a CFG node.

isSequential

public boolean isSequential()

Return true if this is a SequentialChord instance.

isBranch

public boolean isBranch()

Return true if this CFG node may have multiple out-going CFG edges.

isLoopHeader

public boolean isLoopHeader()

Return true if this CFG node is a LoopHeaderChord instance.

isLoopPreHeader

public boolean isLoopPreHeader()

Return true if this CFG node is a LoopPreHeaderChord instance.

isLoopExit

public boolean isLoopExit()

Return true if this CFG node is a LoopExitChord instance.

isLoopTail

public boolean isLoopTail()

Return true if this CFG node is a LoopTailChord instance.

isPhiExpr

public boolean isPhiExpr()

Return true if this CFG node is a PhiExprChord instance.

isSpecial

public boolean isSpecial()

Return true if this is CFG node was added for the convenience of the compiler and does not correspond to actual source code in the user program.

isMarker

public boolean isMarker()

Return true if this is a marker CFG node.

isExprChord

public boolean isExprChord()

Return true if this is an ExprChord instance.

setVisited

public final void setVisited()

Associate the current color value with a CFG node. The color is for the use of CFG spanning algorithms.

See Also:

nextVisit(), visited(), pushOutCfgEdges(scale.common.Stack), pushInCfgEdges(scale.common.Stack)

visited

public final boolean visited()

Return true if this CFG node has been visited during the current visit (i.e., is the current color).

See Also:

nextVisit(), setVisited(), pushOutCfgEdges(scale.common.Stack), pushInCfgEdges(scale.common.Stack)

parentsVisited

public boolean parentsVisited()

Return true if the parents of this CFG node have been visited.

parentsFinished

public boolean parentsFinished(HashSet<Chord> finished)

Return true if all predecessor CFG nodes are in the finished set.

Parameters:

finished - is the set to test.

pushAllOutCfgEdges

public abstract void pushAllOutCfgEdges(Stack<Chord> wl)

Add the successors of this CFG node to the stack.

pushOutCfgEdges

public abstract void pushOutCfgEdges(Stack<Chord> wl)

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

See Also:

nextVisit(), setVisited(), visited()

pushOutCfgEdges

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

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

Parameters:

done - is the set of visited CFG nodes

pushSortedOutCfgEdges

public abstract void pushSortedOutCfgEdges(Stack<Chord> wl)

Add the successors of this CFG node 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).

pushSortedOutCfgEdges

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

Add the successors of this CFG node 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).

Parameters:

finished - is the set of finished nodes.

pushInCfgEdges

public final void pushInCfgEdges(Stack<Chord> wl)

Add the predecessors of this CFG node to the stack if they haven't been visited before.

See Also:

nextVisit(), setVisited(), visited()

pushInCfgEdges

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

Add the predecessors of this CFG node to the stack if they haven't been visited before.

Parameters:

done - is the set of visited CFG nodes

pushAllInCfgEdges

public final void pushAllInCfgEdges(Stack<Chord> wl)

Add the predecessors of this CFG node to the stack.

pushChordWhenReady

public final int pushChordWhenReady(Stack<Chord> wl,
                                    int label)

Place this CFG node on the stack when all its predecessor nodes have been visited. Assign it a label value and increment the label value by one. Note that CFG nodes past a loop exit may be pushed, and given lower label values, even though CFG nodes in the loop have not been visited. If this matters, you may want to use LoopHeaderChord.labelCFGLoopOrder().

Returns:

the new label value

See Also:

Scribble.labelCFG()

pushChordWhenReady

public final void pushChordWhenReady(Stack<Chord> wl)

Place this CFG node on the stack when all its predecessor nodes have been visited. Note that CFG nodes past a loop exit may be pushed even though CFG nodes in the loop have not been visited.

See Also:

Scribble.linearize(scale.common.Vector)

getDisplayLabel

public java.lang.String getDisplayLabel()

Return a String suitable for labeling this node in a graphical display. This method should be over-ridden as it simplay returns the class name.

Specified by:

getDisplayLabel in interface DisplayNode

Overrides:

getDisplayLabel in class Root

getDisplayColorHint

public DColor getDisplayColorHint()

Return a String specifying the color to use for coloring this node in a graphical display. This method should be over-ridden as it simplay returns the color lightblue.

Specified by:

getDisplayColorHint in interface DisplayNode

Overrides:

getDisplayColorHint in class Root

See Also:

DColor

getDisplayShapeHint

public DShape getDisplayShapeHint()

Return a String specifying a shape to use when drawing this node in a graphical display. This method should be over-ridden as it simplay returns the shape "ellipse".

Specified by:

getDisplayShapeHint in interface DisplayNode

Overrides:

getDisplayShapeHint in class Root

See Also:

DShape

copy

public abstract Chord copy()

Make a copy of this CFG node with the same out-going CFG edges. The validity of the CFG graph is maintained.

Returns:

a copy of this node

removeFromCfg

public final void removeFromCfg()

Remove myself from the CFG. This only works for nodes with only one out CFG edge or nodes with no in CFG edges. The validity of the CFG graph is maintained.

Each node in the CFG has a link back to the nodes that point to it. When a node is removed using removeFromCfg (), the nodes that point to the node being removed are changed to point to the successor of the node being removed. It can't do this if there is more than one successor. It this way, the node is removed but the CFG graph remains valid.

The expungeFromCfg() method does not link the parent nodes to the successor node. It breaks the CFG graph. It is up to the calling method to insure that the CFG graph is valid.

See Also:

expungeFromCfg()

unlinkChord

public void unlinkChord()

Break any un-needed links from a CFG node that is being deleted.

extractFromCfg

public final void extractFromCfg()

Remove myself from the CFG but preserve me for future use. This only works for nodes with only one out CFG edge or nodes with no in CFG edges. The validity of the CFG graph is maintained.

Each node in the CFG has a link back to the nodes that point to it. When a node is removed using removeFromCfg(), the nodes that point to the node being removed are changed to point to the successor of the node being removed. It can't do this if there is more than one successor. It this way, the node is removed but the CFG graph remains valid.

The <expungeFromCfg() method does not link the parent nodes to the successor node. It breaks the CFG graph. It is up to the calling method to insure that the CFG graph is valid.

See Also:

expungeFromCfg()

removeDeadCode

public static void removeDeadCode(Stack<Chord> chords)

Remove any CFG nodes that do not have an incoming CFG edge and any un-needed nodes from the CFG. It doesn't remove loops that are dead code. Un-needed nodes include NullChord and GotoChord nodes.

Parameters:

chords - a list of all statement nodes to be checked.

replaceOutCfgEdge

public abstract void replaceOutCfgEdge(Chord oldChord,
                                       Chord newChord)

Replace the existing out-going CFG edge with a new edge. Maintaining the validity of the CFG graph is the responsibility of the caller.

Parameters:

oldChord - is the old edge

newChord - is the new edge

replaceInCfgEdge

public final void replaceInCfgEdge(Chord oldChord,
                                   Chord newChord)

Replace the existing in-coming CFG edge with a new edge. If the old edge is not found, the new edge is added. Maintaining the validity of the CFG graph is the responsibility of the caller.

Parameters:

oldChord - is the old edge

newChord - is the new edge

expungeFromCfg

public final void expungeFromCfg()

Remove myself from the CFG. Maintaining the validity of the CFG is the responsibility of the caller.

See Also:

removeFromCfg()

insertBeforeInCfg

public final void insertBeforeInCfg(SequentialChord newChord)

Insert a new node before me in the CFG. It inherits all of my in-coming Cfg edges. The validity of the CFG is maintained.

Parameters:

newChord - the node to be inserted.

linkTo

public void linkTo(Chord child)

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

insertAfterOutCfg

public final void insertAfterOutCfg(Chord newChord,
                                    Chord outEdge)

Insert a new node between me and my out-going CFG edges. The new node inherits all of my out-going CFG edges. The validity of the CFG is maintained.

Parameters:

newChord - the node to be inserted.

outEdge - is my out-going CFG edge

addInCfgEdge

public void addInCfgEdge(Chord node)

Add an in-coming CFG edge. Maintaining the validity of the CFG is the responsibility of the caller.

Parameters:

node - CFG node which is pointing to me

deleteInCfgEdge

public final void deleteInCfgEdge(Chord node)

Remove an in-coming CFG edge. Maintaining the validity of the CFG is the responsibility of the caller.

Parameters:

node - specifies the in-coming CFG edge

getInCfgEdgeArray

public final Chord[] getInCfgEdgeArray()

Use this method when you may be modifying an in-coming CFG edge to this CFG node while iterating over the in-coming edges.

Returns:

an enumeration of the in-coming CFG edges.

getInCfgEdge

public final Chord getInCfgEdge()

Return the predecessor node. If there is more than one predecessor CFG node, this method will return null.

getFirstInCfgEdge

public final Chord getFirstInCfgEdge()

Return the predecessor node. If there is more than one predecessor CFG node, this method will return one of them. If there is none, null is returned.

getInCfgEdge

public final Chord getInCfgEdge(int i)

Return the i-th predecessor node. Caution must be used when using this method while adding or removinge nodes from the CFG.

numInCfgEdges

public final int numInCfgEdges()

Return the number of in-coming CFG edges.

indexOfInCfgEdge

public final int indexOfInCfgEdge(Chord in)

Return the index of the specified in-coming CFG edge. Return -1 if it's not an edge.

nthIndexOfInCfgEdge

public final int nthIndexOfInCfgEdge(Chord in,
                                     int n)

Return the index of the nth occurrence of the specified in-coming CFG edge. This uses 0-origin indexing. Return -1 if it's not an edge.

numOfInCfgEdge

public int numOfInCfgEdge(Chord in)

Return the number of duplicate in-coming CFG edges from the specified node.

changeParentOutCfgEdge

public final void changeParentOutCfgEdge(Chord newEdge)

Change all my predecessors to point to another CFG node.

firstInBasicBlock

public final Chord firstInBasicBlock()

Return the first CFG node in this basic block.

See Also:

isFirstInBasicBlock(), isLastInBasicBlock(), lastInBasicBlock()

isFirstInBasicBlock

public final boolean isFirstInBasicBlock()

Return true if this CFG node is the start of a basic block. A basic block begins with a node that has more than one in-coming CFG edge or whose predecessor has more than one out-going CFG edge.

See Also:

firstInBasicBlock(), isLastInBasicBlock(), lastInBasicBlock()

isLastInBasicBlock

public abstract boolean isLastInBasicBlock()

Return true if this is the last CFG node in this basic block.

See Also:

lastInBasicBlock(), isFirstInBasicBlock(), firstInBasicBlock()

lastInBasicBlock

public final Chord lastInBasicBlock()

Return the last CFG node in this basic block.

See Also:

isLastInBasicBlock(), isFirstInBasicBlock(), firstInBasicBlock()

getNextChord

public abstract Chord getNextChord()

Return the next CFG node in the CFG. If the there is more than one, return null.

numOutCfgEdges

public abstract int numOutCfgEdges()

Return the number of out-going CFG edges.

getOutCfgEdge

public abstract Chord getOutCfgEdge(int i)

Return the specified out-going CFG edge.

getOutCfgEdgeArray

public abstract Chord[] getOutCfgEdgeArray()

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

Returns:

an array of all of the out-going CFG edges

changeOutCfgEdge

public abstract 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 is maintained.

Parameters:

oldEdge - the out-going CFG edge to be changed

newEdge - the new out-going CFG edge

getInDataEdgeArray

public Expr[] getInDataEdgeArray()

Use this method when you may be modifying an in-coming data edge to this expression while iterating over the in-coming edges.

Specified by:

getInDataEdgeArray in class Note

Returns:

an array of in-coming data edges.

getInDataEdge

public Expr getInDataEdge(int i)

Return the specified in-coming data edge.

Specified by:

getInDataEdge in class Note

numInDataEdges

public int numInDataEdges()

Return the number of in-coming data edges.

Specified by:

numInDataEdges in class Note

pushInDataEdges

public void pushInDataEdges(Stack<Expr> wl)

Push all incoming data edges on the stack.

changeInDataEdge

public void changeInDataEdge(Expr oldExpr,
                             Expr newExpr)

This method changes an incoming data edge to point to a new expression.

This method ensures that the node previously pointing to this one is updated properly, as well as the node which will now point to this node.

Expr instances and CFG nodes have a fixed number of incoming data edges with specific meaning applied to each.

Specified by:

changeInDataEdge in class Note

Parameters:

oldExpr - is the expression to be replaced

newExpr - is the new expression

indexOfOutCfgEdge

public abstract int indexOfOutCfgEdge(Chord to,
                                      int skip)

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

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.

deleteInDataEdges

public abstract void deleteInDataEdges()

Remove all the in-coming data edges.

deleteOutCfgEdges

public abstract void deleteOutCfgEdges()

Remove all the out-going CFG edges.

clearEdgeMarkers

public abstract void clearEdgeMarkers()

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

edgeMarked

public abstract boolean edgeMarked(int edge)

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

Parameters:

edge - specifies the edge associated with the marker

Returns:

true is the specified edge is marked

markEdge

public abstract void markEdge(int edge)

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

Parameters:

edge - specifies the edge associated with the marker

clearEdge

public abstract void clearEdge(int edge)

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

Parameters:

edge - specifies the edge associated with the marker

getDefExpr

public Expr getDefExpr()

If this CFG node results in a variable being given a new value, return the Expr instance that specifies the variable.

Returns:

a null or a Expr instance that defines a variable

getSourceLineNumber

public final int getSourceLineNumber()

Return the source line number associated with this node or -1 if not known.

setSourceLineNumber

public final void setSourceLineNumber(int lineNumber)

Set the source line number associated with this node.

copySourceLine

public void copySourceLine(Chord from)

Copy the source line information.

executionOrder

public int executionOrder(Chord n)

Determine the execution ordering of the two CFG nodes. This routine returns either 0, 1, or -1 based on the following conditions:

• 0 if this and n are in the same CFG node.
• 1 if this occurs before n.
• -1 if n occurs before this.

NOTE - this method will not perform correctly if the Chords have not been labeled.

Parameters:

n - the node to compare against.

Returns:

0, 1, or -1 based upon the lexical ordering.

See Also:

Scribble.labelCFG()

getLoopHeader

public LoopHeaderChord getLoopHeader()

Return the LoopHeaderChord object for the loop that contains this node. The method will return a null if the CFG node is not connected.

For LoopInitChord and LoopPreHeaderChord instances, this method returns the loop header for the loop that they are in - not the loop header for which they are the initial nodes.

getLoopHeader

public LoopHeaderChord getLoopHeader(int limit)

Return the LoopHeaderChord object for the loop that contains this node. The method will return a null if the CFG node is not connected.

For LoopInitChord and LoopPreHeaderChord instances, this method returns the loop header for the loop that they are in - not the loop header for which they are the initial nodes.

Parameters:

limit - is a limit on how many nodes are checked before we give up

getLoopNumber

public int getLoopNumber()

findPhiChords

public Vector<PhiExprChord> findPhiChords()

Return a vector of all of the phi chords in the basic block starting at this node.

loopClean

public void loopClean()

Eliminate associated loop information.

isAssignChord

public boolean isAssignChord()

Return true if this node holds an expression that represents an assignment statement.

inBasicBlock

public final boolean inBasicBlock(Chord first)

Return true if this CFG node is in the basic block specified by first.

findLoopExit

public LoopExitChord findLoopExit(LoopHeaderChord header)

Return the LoopExitChord instance, for the specified loop, that is reachable from this CFG node. Return null if none is found.

getCall

public CallExpr getCall(boolean ignorePure)

Return the call expression or null if none.

Parameters:

ignorePure - is true if pure function calls are to be ignored.

getDeclList

public abstract Vector<Declaration> getDeclList()

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

getLoadExprList

public abstract Vector<LoadExpr> getLoadExprList()

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

getExprList

public abstract Vector<Expr> getExprList()

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

replaceDecl

public abstract boolean replaceDecl(Declaration oldDecl,
                                    Declaration newDecl)

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

removeUseDef

public abstract void removeUseDef()

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

linkSubgraph

public abstract 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.

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)

reorderInCfgEdgesOfCopy

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

Reorder the incoming CFG edges of a new CFG node to match the order of the in-coming edges of the this CFG node.

Parameters:

nm - is the mapping from old nodes to new nodes

See Also:

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

recordRefs

public void recordRefs(References refs)

Record any variable references in this CFG node in the table of references.

removeRefs

public void removeRefs(References refs)

Remove any variable references in this CFG node from the table of references.

removeDualExprs

public boolean removeDualExprs()

Remove all DualExpr instances from the CFG. Use the lower form. This eliminates references to variables that may no longer be needed.

toStringSpecial

public java.lang.String toStringSpecial()

Return a String containing additional information about this CFG node.

Overrides:

toStringSpecial in class Root