scale.score.chords
Class SwitchChord

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

All Implemented Interfaces:

AnnotationInterface, DisplayNode

public class SwitchChord
extends DecisionChord

This class represents a Scribble CFG node that has multiple out-going CFG edges.

$Id: SwitchChord.java,v 1.39 2007-10-04 19:58:23 burrill Exp $

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

This is the base class for all classes that have more than one out-going CFG edge. The edges are selected using a key object.

Field Summary

Fields inherited from class scale.score.chords.Chord

lineNumber

Constructor Summary

SwitchChord(Expr predicate)
Create a Chord that has more than one out-going CFG edge where the edge is selected by some computation.

SwitchChord(Expr predicate, Vector<java.lang.Object> keys, Vector<Chord> targets)
Create a Chord that has more than one out-going CFG edge where the edge is selected by some computation.

Method Summary

void	addBranchEdge(java.lang.Object key, Chord target) This method adds changes an out-going CFG edge of the branch.
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.
Chord	copy() Make a copy of this Chord with the same out-going CFG edges.
static int	created() Return the number of instances of this class that were created.
void	deleteOutCfgEdges() Set both out-going CFG edges 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.
int	getBranchEdgeIndex(java.lang.Object key) Return the index of the selected out-going CFG edge.
long[]	getBranchEdgeKeyArray() Return an array of all of the keys used.
double	getBranchProbability(Chord edge) Return the probability that the specified edge will be executed next.
int	getDefaultIndex() Return the index of the default case or -1 if none.
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.
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.
void	linkSubgraph(HashMap<Chord,Chord> nm) Link a new CFG node that contains old links.
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	replaceOutCfgEdge(Chord oldChord, Chord newChord) Replace the existing out-going CFG edge with a new edge.
void	specifyBranchProbability(Chord edge, double probability) Specify the probability that the specified edge will be executed next.
void	visit(Predicate p) Process a node by calling its associated routine.

Methods inherited from class scale.score.chords.DecisionChord

changeInDataEdge, deleteInDataEdges, getDeclList, getDisplayColorHint, getDisplayShapeHint, getExprList, getInDataEdge, getInDataEdgeArray, getLoadExprList, getNextChord, getPredicateExpr, isBranch, isLastInBasicBlock, numInDataEdges, pushInDataEdges, recordRefs, removeDualExprs, removeRefs, removeUseDef, replaceDecl, toStringSpecial, validate

Methods inherited from class scale.score.chords.Chord

addInCfgEdge, changeParentOutCfgEdge, copySourceLine, deadCFGNodes, deletedCFGNodes, deleteInCfgEdge, executionOrder, expungeFromCfg, extractFromCfg, findLoopExit, findPhiChords, firstInBasicBlock, getCall, getDefExpr, getDisplayLabel, getFirstInCfgEdge, getInCfgEdge, getInCfgEdge, getInCfgEdgeArray, getLabel, getLoopHeader, getLoopHeader, getLoopNumber, getSourceLineNumber, gotoCFGNodes, inBasicBlock, indexOfInCfgEdge, insertAfterOutCfg, insertBeforeInCfg, isAssignChord, isExprChord, isFirstInBasicBlock, isLoopExit, isLoopHeader, isLoopPreHeader, isLoopTail, isMarker, isPhiExpr, isSequential, isSpecial, lastInBasicBlock, linkTo, loopClean, nextVisit, nthIndexOfInCfgEdge, nullCFGNodes, numInCfgEdges, numOfInCfgEdge, parentsFinished, parentsVisited, pushAllInCfgEdges, pushChordWhenReady, pushChordWhenReady, pushInCfgEdges, pushInCfgEdges, removeDeadCode, removeFromCfg, reorderInCfgEdgesOfCopy, replaceInCfgEdge, setLabel, setSourceLineNumber, setVisited, unlinkChord, visited

Methods inherited from class scale.score.Note

getChord, getEssentialUse, setAnnotationLevel, setReportLevel, toString

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

SwitchChord

public SwitchChord(Expr predicate,
                   Vector<java.lang.Object> keys,
                   Vector<Chord> targets)

Create a Chord that has more than one out-going CFG edge where the edge is selected by some computation.

Parameters:

predicate - the expression which is evaluated to select the out-going edge

keys - a vector of keys associated with the out-going edges

targets - a vector of out-going CFG edges

SwitchChord

public SwitchChord(Expr predicate)

Create a Chord that has more than one out-going CFG edge where the edge is selected by some computation.

Parameters:

predicate - the expression which is evaluated to select the out-going edge

Method Detail

created

public static int created()

Return the number of instances of this class that were created.

visit

public void visit(Predicate p)

Description copied from class: Note

Process a node by calling its associated routine. See the "visitor" design pattern in Design Patterns: Elements of Reusable Object-Oriented Software by E. Gamma, et al, Addison Wesley, ISBN 0-201-63361-2.

Each class has a visit(Predicate p) method. For example, in class ABC:

   public void visit(Predicate p)
   {
     p.visitABC(this);
   }
 

and the class that implements Predicate has a method

   public void visitABC(Note n)
   {
     ABC a = (ABC) n;
     ...
   }
 

Thus, the class that implements Predicate can call

   n.visit(this);
 

where n is a Note sub-class without determining which specific sub-class n is. The visit pattern basically avoids implementing a large switch statement or defining different methods in each class for some purpose.

Specified by:

visit in class Note

See Also:

Predicate

deleteOutCfgEdges

public void deleteOutCfgEdges()

Set both out-going CFG edges to null. This method does not maintain the validity of the CFG as the nodes at the other ends of the edges are not modified.

Specified by:

deleteOutCfgEdges in class Chord

copy

public Chord copy()

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

Specified by:

copy in class Chord

Returns:

a copy of this node

getBranchEdgeIndex

public int getBranchEdgeIndex(java.lang.Object key)

Return the index of the selected out-going CFG edge.

Specified by:

getBranchEdgeIndex in class DecisionChord

Parameters:

key - specifies the out-going CFG edge

replaceOutCfgEdge

public 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

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

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.

getBranchEdgeKeyArray

public final long[] getBranchEdgeKeyArray()

Return an array of all of the keys used. They are guaranteed to be in the same order as the CFG out-going edges.

getDefaultIndex

public final int getDefaultIndex()

Return the index of the default case or -1 if none.

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. They are guaranteed to be in the same order as the branch arm keys.

addBranchEdge

public void addBranchEdge(java.lang.Object key,
                          Chord target)

This method adds changes an out-going CFG edge of the branch. It is a lot like ChangeOutCfgEdge, except that it manages the pairing of branch target with key value. The validity of the CFG graph is maintained.

Parameters:

key - When predicate evaluates to this value, the associated branch will be taken.

target - Target of branch associated with this key.

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

specifyBranchProbability

public final void specifyBranchProbability(Chord edge,
                                           double probability)

Specify the probability that the specified edge will be executed next. The stored value for the probability is quantized for reasons of space utilization. The probability of both edges is set. The sum of the probabilities of both edges is always (approximately) 1.0.

Specified by:

specifyBranchProbability in class DecisionChord

getBranchProbability

public final double getBranchProbability(Chord edge)

Return the probability that the specified edge will be executed next. If there are multiple out-going CFG edges to the same CFG node, the probability is the sum of the probability of all the edges to that node. The stored value for the probability is quantized for reasons of space utilization. The sum of the probabilities of both edges is always (approximately) 1.0.

Specified by:

getBranchProbability in class DecisionChord

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

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

Specified by:

clearEdgeMarkers in class Chord

edgeMarked

public 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

See Also:

getOutCfgEdge(int)

markEdge

public 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

See Also:

getOutCfgEdge(int)

clearEdge

public 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

See Also:

getOutCfgEdge(int)

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