scale.score.expr
Class Expr

java.lang.Object
  |
  +--scale.common.Root
        |
        +--scale.score.Note
              |
              +--scale.score.expr.Expr
All Implemented Interfaces:
AnnotationInterface, DisplayNode, java.io.Serializable
Direct Known Subclasses:
BinaryExpr, DualExpr, LoadExpr, NaryExpr, SubscriptExpr, TernaryExpr, UnaryExpr, ValueExpr, VarArgExpr

public abstract class Expr
extends Note

The base class for Score expression classes.

$Id: Expr.java,v 1.75 2002/01/15 15:22:46 burrill Exp $

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

All expression objects have an associated type.

An expression is an operation plus some number of arguments. Each argument is an expression node as well. The result of an expression may propagate to another expression (as one of its arguments) or to other nodes (e.g., statememts).

An expression node has a fixed number of incoming data edges (i.e., its operands) and an unlimited number of outgoing data edges.

As modeled by this class, an expression has some number of operands which are represented as incoming data edges, and a result which is represented as outgoing data edges. Some expressions have extra information which is not an operand. This information is sometimes properly part of the operator (e.g., the error handling indicator on arithmetic operators), and sometimes it is not even that (e.g., the value of a literal). This extra information is in some sense not part of the Score graph (i.e., these are non-graph edges).

See Also:
Serialized Form

Field Summary
static int SE_DOMAIN
          Side effect - may cause fault because of domain values.
static int SE_NONE
          Side effect - none.
static int SE_OVERFLOW
          Side effect - may cause overflow or underflow fault.
static int SE_STATE
          Side effect - changes some global state (e.g., memory location)
 
Fields inherited from interface scale.common.DisplayNode
ANNO, CLEF, DD, DEFUSE, DOM, EXPR, MAYUSE, TYPE
 
Constructor Summary
protected Expr()
           
protected Expr(Type type)
          Build an expression node.
 
Method Summary
protected  void addInDataEdge(Note node)
          This method adds an in-coming data edge to this node.
 long canonical()
          Return a unique value representing this particular expression.
 void changeInDataEdge(Expr oldExpr, Expr newExpr)
          This method changes an incoming data edge to point to a new expression.
abstract  Expr copy()
          Perform a deep copy of the expression tree.
static int created()
          Return the number of instances of this class that were created.
 java.lang.Integer DDconstantValue()
          If the node represents an expression that is an integer constant, then return the constant value.
 void deleteOutDataEdge(Note node)
          This method deletes the outgoing data edge.
 boolean equivalent(Expr exp)
          Return true if the expressions are equivalent.
 int executionOrder(Expr n)
          Determine the execution ordering of the two nodes.
 int executionOrder(java.util.Stack p1, java.util.Stack p2)
          Determine the lexical order between two nodes with respect to 'this' node.
protected  void finalize()
          Keep the count of instances up-to-date.
protected  int findCriticalChord(HashMap lMap)
           
 int findLinearCoefficient(Expr indexVar, Loop topLoop)
          Return the coefficient of a linear expression.
 CallExpr getCall(boolean ignorePure)
          Return the call expression or null if none.
 java.lang.Object getConstantValue(HashMap cvMap)
          Return the constant value of the expression.
 Type getCoreType()
          Return the core type of the expression.
 int getCriticalChord(HashMap lMap)
          Return the label of the Chord with the highest label value from the set of Chords that must be executed before this expression.
 java.lang.String getDDName()
          If this node represents an identifier, then return the identifier name.
 java.lang.String getDDString()
          Return the string representation of the expression this load expression represents.
 Expr getDefExpr()
          If this expression results in a variable being given a new value, return the LoadExpr that specifies the variable.
 java.lang.String getDisplayColorHint()
          Return a String specifying the color to use for coloring this node in a graphical display.
 java.lang.String getDisplayShapeHint()
          Return a String specifying a shape to use when drawing this node in a graphical display.
 java.lang.String getDisplayText()
          Return a String suitable for labeling this node in a graphical display.
 DualExpr getDualExpr()
          Return the DualExpr containing this SubscriptExpr or null if none.
 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.
 InductionVar getInductionVar()
          Return the induction variable associated with this expression.
 int getLinearity(AffineExpr ae, Loop topLoop)
          Determine if the expression is a linear function.
 Loop getLoop()
          Return the node which represents the loop that contains this node.
 Loop getLoopIndexLoop()
           
 Expr getLValue()
          Return the lvalue if this statement is an assignment statement.
 Expr getOperand(int position)
          Return the specified operand.
 Expr[] getOperandArray()
          Return an array of the operands to the expression.
 Note getOutDataEdge()
          Return the out-going data edge.
 Expr getReference()
          Return the variable reference for the expression.
 Expr getRValue()
          Return the rvalue if this statement is an assignment statement.
 Type getType()
          Return the type of the expression.
 AffineExpr isAffine()
          Determine if this expression represents an affine expression.
 boolean isDefined()
          This method determines if this expression's value is defined or used by the expression.
 boolean isDefined(Expr lv)
          Check if the given expression is defined by this expression.
 boolean isLoopIndex()
          Return true if this expression is the loop index expression.
 boolean isMemoryDef()
          Return true if the node reference is a definition.
 boolean isPrimaryLoopIndex()
          Return true if this expression is the primary loop index expression.
 boolean isScalar()
          Return true if this expression represents an operation that uses scalar types.
 void loopClean()
          Clean up any loop related information.
 int numArguments()
          Return the number of expression arguments.
static int number()
          Return the current number of instances of this class.
 int numInDataEdges()
          Return the number of in-coming data edges.
 int numOperands()
          Return the number of operands to this expression.
 void removeRefInfo()
          Remove any information such as use - def links, may use links, etc.
protected  Expr setOperand(Expr operand, int position)
          Set the nth operand of an expression.
 void setOutDataEdge(Note node)
          This method adds an outgoing data edge to this node.
 void setType(Type type)
          Set the type of the expression.
 int sideEffects()
          Return an indication of the side effects execution of this expression may cause.
 java.lang.String toStringSpecial()
          Return any special information of a node that is not a child or annotation.
 void unlinkExpression()
          If the node is no longer needed, sever its use-def link, etc.
 boolean validLValue()
          Return true if this expression is valid on the left side of an assignment.
 
Methods inherited from class scale.score.Note
getChord, setAnnotationLevel, setReportLevel, toString, visit
 
Methods inherited from class scale.common.Root
addAnnotation, allAnnotations, allMatchingAnnotations, getAnnotation, getDisplayName, getDisplayString, getNodeCount, getNodeID, hasAnnotation, hasEqualAnnotation, hashCode, removeAnnotation, removeAnnotations, toStringAnnotations, toStringClass
 
Methods inherited from class java.lang.Object
clone, equals, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

SE_NONE

public static final int SE_NONE
Side effect - none.

SE_OVERFLOW

public static final int SE_OVERFLOW
Side effect - may cause overflow or underflow fault.

SE_DOMAIN

public static final int SE_DOMAIN
Side effect - may cause fault because of domain values.

SE_STATE

public static final int SE_STATE
Side effect - changes some global state (e.g., memory location)
Constructor Detail

Expr

protected Expr(Type type)
Build an expression node.
Parameters:
type - is the type of the value that results from this expression.

Expr

protected Expr()
Method Detail

finalize

protected void finalize()
                 throws java.lang.Throwable
Keep the count of instances up-to-date.
Overrides:
finalize in class java.lang.Object
Throws:
java.lang.Throwable - [needs description]

number

public static int number()
Return the current number of instances of this class.

created

public static int created()
Return the number of instances of this class that were created.

sideEffects

public int sideEffects()
Return an indication of the side effects execution of this expression may cause.
See Also:
SE_NONE

equivalent

public boolean equivalent(Expr exp)
Return true if the expressions are equivalent. This method should be called by the equivalent() method of the derived classes.
Returns:
true if classes are identical and the core types are equivalent

getDisplayText

public java.lang.String getDisplayText()
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.
Overrides:
getDisplayText in class Root

getDisplayColorHint

public java.lang.String 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 red.
Overrides:
getDisplayColorHint in class Root

getDisplayShapeHint

public java.lang.String 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 "box".
Overrides:
getDisplayShapeHint in class Root

getType

public final Type getType()
Return the type of the expression.

getCoreType

public final Type getCoreType()
Return the core type of the expression.

setType

public final void setType(Type type)
Set the type of the expression.
Parameters:
t - the type of the expression

copy

public abstract Expr copy()
Perform a deep copy of the expression tree. By deep copy, we mean that copies are made of the expression tree.
Returns:
a copy of this expression

setOperand

protected Expr setOperand(Expr operand,
                          int position)
Set the nth operand of an expression.
Parameters:
node - - the new operand
position - - indicates which operand
Returns:
the previous operand

getOperand

public Expr getOperand(int position)
Return the specified operand.
Parameters:
position - is the index of the operand

getOperandArray

public Expr[] getOperandArray()
Return an array of the operands to the expression.

numOperands

public int numOperands()
Return the number of operands to this expression.

numArguments

public int numArguments()
Return the number of expression arguments.

numInDataEdges

public int numInDataEdges()
Return the number of in-coming data edges.
Overrides:
numInDataEdges in class Note

isDefined

public boolean isDefined(Expr lv)
Check if the given expression is defined by this expression.
Parameters:
expr - the given expression to check.
Returns:
true if this statement is an assignment statement and expr ` * appear on the LHS is the lvalue.

isDefined

public boolean isDefined()
This method determines if this expression's value is defined or used by the expression. We return true if the value is defined.
Returns:
true if this expression's value is defined.

getReference

public Expr getReference()
Return the variable reference for the expression. We use this to get the variable reference for operations such as array subscript and structure operations.
Returns:
null since a general expression doesn't have a variable

getLValue

public Expr getLValue()
Return the lvalue if this statement is an assignment statement.

getRValue

public Expr getRValue()
Return the rvalue if this statement is an assignment statement.

addInDataEdge

protected void addInDataEdge(Note node)
This method adds an in-coming data edge to this node.
Overrides:
addInDataEdge in class Note
Parameters:
node - Note to which this out edge is pointing

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.
Overrides:
getInDataEdgeArray in class Note
Returns:
an array of in-coming data edges.

getOutDataEdge

public Note getOutDataEdge()
Return the out-going data edge.

setOutDataEdge

public final void setOutDataEdge(Note node)
This method adds an outgoing data edge to this node. Only expression nodes have an outbound data edge.
Parameters:
node - Note to which this out edge is pointing

changeInDataEdge

public final 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 and Chord nodes have a fixed number of incoming edges with specific meaning applied to each. Hence, the edge being replaced is indicated by position.

Overrides:
changeInDataEdge in class Note
Parameters:
oldExpr - is the expression to be replaced
newExpr - is the new expression

deleteOutDataEdge

public final void deleteOutDataEdge(Note node)
This method deletes the outgoing data edge.

This method is a helper routine. It intended to aid another routine which deleting this edge as an incoming edge. The two methods work together to maintain bi-directional edges.

Only one outgoing edge per call will be deleted. Hence, if this node has multiple edges to the indicated node, only one of them will be deleted. Because outgoing edges are not ordered, for a node pair with multiple edges, this method may pick a random instance.

Because only expression nodes have outgoing edges, this method only applies to expression nodes. Other kinds of nodes should throw an exception.

Parameters:
node - Indicates edge to be deleted, by designating its opposite end.

toStringSpecial

public java.lang.String toStringSpecial()
Description copied from class: Root
Return any special information of a node that is not a child or annotation. This method is meant to be overridden by nodes that need to provide special output.
Overrides:
toStringSpecial in class Root

getConstantValue

public java.lang.Object getConstantValue(HashMap cvMap)
Return the constant value of the expression.
See Also:
Lattice

findCriticalChord

protected int findCriticalChord(HashMap lMap)

getCriticalChord

public final int getCriticalChord(HashMap lMap)
Return the label of the Chord with the highest label value from the set of Chords that must be executed before this expression.

isScalar

public boolean isScalar()
Return true if this expression represents an operation that uses scalar types.

canonical

public long canonical()
Return a unique value representing this particular expression.

validLValue

public boolean validLValue()
Return true if this expression is valid on the left side of an assignment.

removeRefInfo

public void removeRefInfo()
Remove any information such as use - def links, may use links, etc.

getDefExpr

public Expr getDefExpr()
If this expression results in a variable being given a new value, return the LoadExpr that specifies the variable.
Returns:
a null or a LoadExpr that defines a variable

executionOrder

public int executionOrder(Expr n)
Determine the execution ordering of the two 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 on the same side of the assignment.
 1 if this occurs before n.
 -1 if n occurs before this.
 
Two nodes are equivalent if we can't determine that one defintely occurs before the other (e.g., in an assignment statement, a[i] = a[i-1], the execution order is not defined.

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:
Chord.executionOrder(scale.score.chords.Chord), Scribble.labelCFG()

getLoop

public Loop getLoop()
Return the node which represents the loop that contains this node.

getDDName

public java.lang.String getDDName()
If this node represents an identifier, then return the identifier name.
Returns:
the identifier name.

isMemoryDef

public boolean isMemoryDef()
Return true if the node reference is a definition. That is, does this node represents a write to a memory location.

DDconstantValue

public java.lang.Integer DDconstantValue()
If the node represents an expression that is an integer constant, then return the constant value. If the node is not a integer constant, then return null.
Returns:
the constant value of the node.

getLinearity

public int getLinearity(AffineExpr ae,
                        Loop topLoop)
Determine if the expression is a linear function. That is the expression is of the form c0 + c1*a1 + ... + cN*aN. The function return a 'linearity' value. Values less than or equal to one indicate a linear expression. Other values indicate the expression is not linear. A general Clef node is not lenear.
Returns:
the linearity value.

findLinearCoefficient

public int findLinearCoefficient(Expr indexVar,
                                 Loop topLoop)
Return the coefficient of a linear expression. Typically, we are trying to determine if an array subscript expression is a linear function of the loop index expression. A general Clef node does not have a coefficient.

executionOrder

public int executionOrder(java.util.Stack p1,
                          java.util.Stack p2)
Determine the lexical order between two nodes with respect to 'this' node. We check this by examining the paths of the two nodes to the children of 'this' node.
Parameters:
p1 - the parent path of a node.
p2 - the parent path of another node.
Returns:
0, 1, or -1 depending upon the lexical ordering.

getDDString

public java.lang.String getDDString()
Return the string representation of the expression this load expression represents.

isLoopIndex

public boolean isLoopIndex()
Return true if this expression is the loop index expression.

getInductionVar

public InductionVar getInductionVar()
Return the induction variable associated with this expression.

getLoopIndexLoop

public Loop getLoopIndexLoop()

isPrimaryLoopIndex

public boolean isPrimaryLoopIndex()
Return true if this expression is the primary loop index expression.

getDualExpr

public final DualExpr getDualExpr()
Return the DualExpr containing this SubscriptExpr or null if none. Follow the use-def chain if necessary.

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.

loopClean

public void loopClean()
Clean up any loop related information.

unlinkExpression

public void unlinkExpression()
If the node is no longer needed, sever its use-def link, etc.

isAffine

public AffineExpr isAffine()
Determine if this expression represents an affine expression.
Returns:
the affine expression or null
See Also:
Loop.isAffine(scale.score.expr.Expr)