scale.score.expr
Class PhiExpr

java.lang.Object
  scale.common.Root
      scale.score.Note
          scale.score.expr.Expr
              scale.score.expr.NaryExpr
                  scale.score.expr.PhiExpr

All Implemented Interfaces:

AnnotationInterface, DisplayNode

Direct Known Subclasses:

ExprPhiExpr

public class PhiExpr
extends NaryExpr

This operator represents a phi operation in static single assignment form.

$Id: PhiExpr.java,v 1.71 2007-10-17 13:45:45 burrill Exp $

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

See Also:

SSA

Field Summary

Fields inherited from class scale.score.expr.Expr

fpReorder, SE_DOMAIN, SE_NONE, SE_OVERFLOW, SE_STATE

Constructor Summary

PhiExpr(Type type, Vector<Expr> operands)
Build a phi function instance.

Method Summary

void	clearEdge(int i) Clear the i-th marker.
void	clearEdgeMarkers() Clear all the markers.
Expr	copy() Perform a deep copy of the expression tree.
boolean	dependsOnDeclaration(Declaration decl) Return true if this expression's value depends on the variable.
boolean	edgeMarked(int i) Return the i-th marker.
int	executionCostEstimate() Return a relative cost estimate for executing the expression.
protected Chord	findCriticalChord(HashMap<Expr,Chord> lMap, Chord independent) Return the Chord with the highest label value from the set of Chords that must be executed before this expression.
int	findLinearCoefficient(VariableDecl indexVar, LoopHeaderChord thisLoop) Determine the coefficent of a linear expression.
protected AffineExpr	getAffineRepresentation(HashMap<Expr,AffineExpr> affines, LoopHeaderChord thisLoop) Return the affine representation for this expression.
Literal	getConstantValue(HashMap<Expr,Literal> cvMap) Return the constant value of the expression.
java.lang.String	getDisplayLabel() Return a String suitable for labeling this node in a graphical display.
boolean	isLoopInvariant(LoopHeaderChord loop) Return true if this expression is loop invariant.
void	markEdge(int i) Set the i-th marker.
boolean	optimizationCandidate() Return true if the expression can be moved without problems.
void	removeOperand(int i) Allow some expressions such as VectorExpr to remove an operand.
int	sideEffects() Return an indication of the side effects execution of this expression may cause.
void	validate() Check this node for validity.
void	visit(Predicate p) Process a node by calling its associated routine.

Methods inherited from class scale.score.expr.NaryExpr

addOperand, containsDeclaration, equivalent, getDeclList, getExprList, getLoadExprList, getOperand, getOperandArray, loopClean, numOperands, pushOperands, recordRefs, removeRefs, removeUseDef, replaceDecl, setOperand, unlinkExpression

Methods inherited from class scale.score.expr.Expr

addCast, addCast, canonical, changeInDataEdge, conditionalCopy, conditionalUnlinkExpression, deleteOutDataEdge, executionOrder, executionOrdinal, findSubscriptExpr, getAffineExpr, getAliasAnnote, getCall, getConstantValue, getCoreType, getCriticalChord, getDefExpr, getDisplayColorHint, getDisplayShapeHint, getDualExpr, getInDataEdge, getInDataEdgeArray, getLoopHeader, getLow, getLValue, getOutDataEdge, getPointedToCore, getReference, getReuseLevel, getRValue, getType, getUseDef, hasTrueFalseResult, isCast, isDefined, isDefined, isLiteralExpr, isMatchExpr, isMemoryDef, isMemRefExpr, isScalar, isSimpleExpr, mayGenerateCall, numInDataEdges, reduce, removeDualExprs, setCrossloopReuse, setOutDataEdge, setSpatialReuse, setStep, setTemporalReuse, setType, setUseDef, toStringSpecial, validLValue

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

PhiExpr

public PhiExpr(Type type,
               Vector<Expr> operands)

Build a phi function instance.

All incoming values should be of the same type. The result type is the same as that of the incoming data.

Parameters:

type - of the result and each argument

operands - a vector of arguments

See Also:

SSA

Method Detail

copy

public Expr copy()

Description copied from class: Expr

Perform a deep copy of the expression tree. By deep copy, we mean that copies are made of the expression tree.

Specified by:

copy in class Expr

Returns:

a copy of this expression

optimizationCandidate

public boolean optimizationCandidate()

Return true if the expression can be moved without problems. Expressions that reference global variables, non-atomic variables, etc are not optimization candidates.

Overrides:

optimizationCandidate in class NaryExpr

sideEffects

public int sideEffects()

Return an indication of the side effects execution of this expression may cause.

Overrides:

sideEffects in class NaryExpr

See Also:

Expr.SE_NONE

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

getDisplayLabel

public java.lang.String getDisplayLabel()

Description copied from class: Expr

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 Expr

removeOperand

public void removeOperand(int i)

Allow some expressions such as VectorExpr to remove an operand.

Overrides:

removeOperand in class NaryExpr

clearEdgeMarkers

public void clearEdgeMarkers()

Clear all the markers. Each marker is associated with one operand of the Phi function.

edgeMarked

public boolean edgeMarked(int i)

Return the i-th marker.

Parameters:

i - the index of the marker

markEdge

public void markEdge(int i)

Set the i-th marker.

Parameters:

i - the index of the marker

clearEdge

public void clearEdge(int i)

Clear the i-th marker.

Parameters:

i - the index of the marker

getConstantValue

public Literal getConstantValue(HashMap<Expr,Literal> cvMap)

Return the constant value of the expression. Follow use-def links.

Overrides:

getConstantValue in class Expr

See Also:

Lattice

findLinearCoefficient

public int findLinearCoefficient(VariableDecl indexVar,
                                 LoopHeaderChord thisLoop)

Determine the coefficent of a linear expression.

Overrides:

findLinearCoefficient in class Expr

Parameters:

indexVar - the index variable associated with the coefficient.

Returns:

the coefficient value.

getAffineRepresentation

protected AffineExpr getAffineRepresentation(HashMap<Expr,AffineExpr> affines,
                                             LoopHeaderChord thisLoop)

Description copied from class: Expr

Return the affine representation for this expression. This method should be called only from the getAffineExpr() method. This method never returns null.

Overrides:

getAffineRepresentation in class Expr

Parameters:

affines - is a mapping from an expression to its representation and is used to avoid combinatorial explosion through use-def links

thisLoop - the loop for which this expression may be affine

See Also:

AffineExpr, AffineExpr.notAffine

isLoopInvariant

public boolean isLoopInvariant(LoopHeaderChord loop)

Return true if this expression is loop invariant.

Overrides:

isLoopInvariant in class Expr

Parameters:

loop - is the loop

findCriticalChord

protected Chord findCriticalChord(HashMap<Expr,Chord> lMap,
                                  Chord independent)

Return the Chord with the highest label value from the set of Chords that must be executed before this expression.

Overrides:

findCriticalChord in class Expr

Parameters:

lMap - is used to memoize the expression to critical Chord information

independent - is returned if the expression is not dependent on anything

dependsOnDeclaration

public boolean dependsOnDeclaration(Declaration decl)

Return true if this expression's value depends on the variable. The use-def links are followed.

Overrides:

dependsOnDeclaration in class NaryExpr

See Also:

LoadExpr.setUseOriginal(boolean)

executionCostEstimate

public int executionCostEstimate()

Return a relative cost estimate for executing the expression.

Overrides:

executionCostEstimate in class NaryExpr

validate

public void validate()

Check this node for validity. This method throws an exception if the node is not linked properly.

Overrides:

validate in class NaryExpr