scale.score.chords
Class IfThenElseChord

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

All Implemented Interfaces:

AnnotationInterface, DisplayNode

public class IfThenElseChord
extends DecisionChord

This class represents a if-then-else statement node in a Scribble CFG.

$Id: IfThenElseChord.java,v 1.41 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.

Field Summary

Fields inherited from class scale.score.chords.Chord

lineNumber

Constructor Summary

IfThenElseChord(Expr predicate)

IfThenElseChord(Expr predicate, Chord trueEdge, Chord falseEdge)

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.
Chord	copy() Make a copy of this CFG node with the same out-going CFG edges.
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.
double	getBranchProbability(Chord edge) Return the probability that the specified edge will be executed next.
Chord	getFalseCfgEdge() Return the edge that is followed if the predicate evaluates to false.
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	getTrueCfgEdge() Return the edge that is followed if the predicate evaluates to true.
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	setFalseEdge(Chord falseEdge) Specify the false out-going CFG edge.
void	setTrueEdge(Chord trueEdge) Specify the true out-going CFG 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

IfThenElseChord

public IfThenElseChord(Expr predicate,
                       Chord trueEdge,
                       Chord falseEdge)

Parameters:

predicate - is the test value

trueEdge - is the next Chord if the predicate evaluates to true

falseEdge - is the next Chord if the predicate evaluates to false

IfThenElseChord

public IfThenElseChord(Expr predicate)

Parameters:

predicate - is the test value

Method Detail

copy

public Chord copy()

Description copied from class: Chord

Make a copy of this CFG node 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

getTrueCfgEdge

public Chord getTrueCfgEdge()

Return the edge that is followed if the predicate evaluates to true.

getFalseCfgEdge

public Chord getFalseCfgEdge()

Return the edge that is followed if the predicate evaluates to false.

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

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

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

setTrueEdge

public void setTrueEdge(Chord trueEdge)

Specify the true out-going CFG edge.

setFalseEdge

public void setFalseEdge(Chord falseEdge)

Specify the false out-going CFG edge.

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

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.

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

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

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)

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

executionCostEstimate

public int executionCostEstimate()

Return a relative cost estimate for executing the expression.

Specified by:

executionCostEstimate in class Note