scale.score.expr
Class Expr

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

All Implemented Interfaces:

AnnotationInterface, DisplayNode

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.160 2007-10-17 13:40:00 burrill Exp $

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

All expression instances have an associated type.

An expression instance is an operation plus some number of arguments. Each argument is an expression instance as well. The value of an expression may propagate to another expression (as one of its operands) or to a CFG node (e.g., ExprChord instance).

An expression instance has a fixed number of incoming data edges (i.e., its operands) and one outgoing data edge.

As modeled by this class, an expression has some number of operands which are represented as incoming data edges, and a value which is represented as the outgoing data edge. Some expression classes have extra information which is not an operand. This information is sometimes properly part of the operator (e.g., the type of conversion for ConversionExpr instances), 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 CFG (i.e., these are non-graph edges).

Since an expression may have only one outgoing data edges an expression instance is not unique in that there may be other instances that are equivalent (identical in a loose sense). The copy() method is provided so that an equivalent expression instance may be created from an exisiting expression instance. Attempting to link in an expression instance that is already linked into the CFG results in a scale.common.InternalError exception.

Memory references are defined by instances of the LoadExpr abstract class and the LoadValueIndirectExpr class.

• A LoadDeclAddressExpr instance on the right-hand-side never references memory - it evaluates to an address.
• A LoadDeclValueExpr instance always causes a memory reference (or register copy).
• A LoadValueIndirectExpr instance always causes a memory reference.

Field Summary

static boolean	fpReorder True if floating point operations may be reordered.
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)

Constructor Summary

protected	Expr()
protected	Expr(Type type) Build an expression node.

Method Summary

Expr	addCast(Expr orig) Add a cast of an address if required.
Expr	addCast(Type orig) Add a cast of an address if required.
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.
Expr	conditionalCopy() Return a deep copy of the expression tree if this expression is used.
void	conditionalUnlinkExpression() If the node is no longer needed, sever its use-def link, etc.
boolean	containsDeclaration(Declaration decl) Return true if this expression contains a reference to the variable.
abstract Expr	copy() Perform a deep copy of the expression tree.
void	deleteOutDataEdge(Note node) This method deletes the outgoing data edge.
boolean	dependsOnDeclaration(Declaration decl) Return true if this expression's value depends on the variable.
boolean	equivalent(Expr exp) Return true if the expressions are equivalent.
int	executionOrder(Expr n) Determine the execution ordering of the two nodes.
int	executionOrdinal() Return the "execution ordinal" of this 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) Return the coefficient of a linear expression.
SubscriptExpr	findSubscriptExpr() Return the SubscriptExpr that this load uses or null if none is found.
AffineExpr	getAffineExpr(HashMap<Expr,AffineExpr> affines, LoopHeaderChord thisLoop) Return the affine representation for this expression or null if it is not affine.
protected AffineExpr	getAffineRepresentation(HashMap<Expr,AffineExpr> affines, LoopHeaderChord thisLoop) Return the affine representation for this expression.
AliasAnnote	getAliasAnnote() Get the alias annotation associated with a Scribble operator.
CallExpr	getCall(boolean ignorePure) Return the call expression or null if none.
Literal	getConstantValue() Return the constant value of the expression.
Literal	getConstantValue(HashMap<Expr,Literal> cvMap) Return the constant value of the expression.
Type	getCoreType() Return the core type of the expression.
Chord	getCriticalChord(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.
abstract void	getDeclList(java.util.AbstractCollection<Declaration> varList) Add all declarations referenced in this expression to the Vector.
Expr	getDefExpr() If this expression results in a variable being given a new value, return the LoadExpr 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.
DualExpr	getDualExpr() Return the DualExpr containing this SubscriptExpr or null if none.
abstract void	getExprList(Vector<Expr> expList) Add all Expr instances in this expression to the Vector.
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.
abstract void	getLoadExprList(Vector<LoadExpr> expList) Add all LoadExpr instances in this expression to the Vector.
LoopHeaderChord	getLoopHeader() Return the node which represents the loop that contains this node.
Expr	getLow() Return the low-level representation.
Expr	getLValue() Return the lvalue if this statement is an assignment statement.
Expr	getOperand(int position) Return the specified operand.
abstract Expr[]	getOperandArray() Return an array of the operands to the expression.
Note	getOutDataEdge() Return the out-going data edge.
Type	getPointedToCore() Return the type of the thing pointed to by the type of the expression.
Expr	getReference() Return the variable reference for the expression.
int	getReuseLevel()
Expr	getRValue() Return the rvalue if this statement is an assignment statement.
Type	getType() Return the type of the expression.
ExprChord	getUseDef() Return the use-def link for the expression.
boolean	hasTrueFalseResult() Return true if the result of the expression is either true (1) or false (0).
boolean	isCast() Return true if this expression is a cast of an address.
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	isLiteralExpr() Return true if this is a literal expression.
boolean	isLoopInvariant(LoopHeaderChord loop) Return true if this expression is loop invariant.
boolean	isMatchExpr() Return true if this is a match expression.
boolean	isMemoryDef() Return true if the node reference is a definition.
boolean	isMemRefExpr() Return true if the expression loads a value from memory.
boolean	isScalar() Return true if this expression represents an operation that uses scalar types.
boolean	isSimpleExpr() Return true if this is a simple expression.
void	loopClean() Clean up any loop related information.
boolean	mayGenerateCall() Return true if this expression may result in the generation of a call to a subroutine.
int	numInDataEdges() Return the number of in-coming data edges.
abstract int	numOperands() Return the number of operands to this expression.
abstract boolean	optimizationCandidate() Return true if the expression can be moved without problems.
abstract void	pushOperands(Stack<Expr> wl) Push all of the operands of this expression on the Stack.
abstract void	recordRefs(Chord stmt, References refs) Record any variable references in this expression in the table of references.
Expr	reduce() Return a simplied equivalent expression.
boolean	removeDualExprs() Remove occurances of DualExpr instances.
abstract void	removeRefs(Chord stmt, References refs) Remove any variable references in this expression from the table of references.
abstract void	removeUseDef() Remove any use - def links, may - use links, etc.
abstract boolean	replaceDecl(Declaration oldDecl, Declaration newDecl) Replace all occurrances of a Declaration with another Declaration.
void	setCrossloopReuse(int level)
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	setSpatialReuse(int level)
void	setStep(int step)
void	setTemporalReuse(int level)
void	setType(Type type) Set the type of the expression.
void	setUseDef(ExprChord se) Set the use-def link for the expression.
abstract 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() This node is no longer needed so sever its use-def link, etc.
void	validate() Check this node for validity.
boolean	validLValue() Return true if this expression is valid on the left side of an assignment.

Methods inherited from class scale.score.Note

executionCostEstimate, getChord, getEssentialUse, 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, trace, trace, trace

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

SE_NONE

public static final int SE_NONE

Side effect - none.

See Also:

Constant Field Values

SE_OVERFLOW

public static final int SE_OVERFLOW

Side effect - may cause overflow or underflow fault.

See Also:

Constant Field Values

SE_DOMAIN

public static final int SE_DOMAIN

Side effect - may cause fault because of domain values.

See Also:

Constant Field Values

SE_STATE

public static final int SE_STATE

Side effect - changes some global state (e.g., memory location)

See Also:

Constant Field Values

fpReorder

public static boolean fpReorder

True if floating point operations may be reordered. Reordering floating point operations may result in the generation of slightly different floating point results by the compiled program. In this case floating point divides may be converted to multiplies by the reciprocal.

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

sideEffects

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

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

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

Specified by:

getDisplayShapeHint in interface DisplayNode

Overrides:

getDisplayShapeHint in class Root

See Also:

DShape

getType

public final Type getType()

Return the type of the expression.

getCoreType

public final Type getCoreType()

Return the core type of the expression.

getPointedToCore

public final Type getPointedToCore()

Return the type of the thing pointed to by the type of the expression. Equivalent to

   getCoreType().getPointedTo().getCoreType()
 

setType

public final void setType(Type type)

Set the type of the expression.

Parameters:

type - is 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

conditionalCopy

public final Expr conditionalCopy()

Return a deep copy of the expression tree if this expression is used. Otherwise, return this expression. By deep copy, we mean that copies are made of all of the nodes in the expression tree. An expression is used if it already has an out-going data edge.

Returns:

a deep copy of this expression or this expression

setOperand

protected Expr setOperand(Expr operand,
                          int position)

Set the nth operand of an expression. This method eliminates the data edge between the previous operand expression and this expression. The new operand must not be null.

Parameters:

operand - - 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 abstract Expr[] getOperandArray()

Return an array of the operands to the expression.

numOperands

public abstract int numOperands()

Return the number of operands to this expression.

getInDataEdge

public final Expr getInDataEdge(int i)

Return the specified in-coming data edge.

Specified by:

getInDataEdge in class Note

numInDataEdges

public final int numInDataEdges()

Return the number of in-coming data edges.

Specified by:

numInDataEdges in class Note

isDefined

public boolean isDefined(Expr lv)

Check if the given expression is defined by this expression.

Parameters:

lv - is the given expression to check.

Returns:

true if this statement is an assignment statement and expr ` * appear on the LHS is the lvalue.

isMatchExpr

public boolean isMatchExpr()

Return true if this is a match expression.

isLiteralExpr

public boolean isLiteralExpr()

Return true if this is a literal expression.

isCast

public boolean isCast()

Return true if this expression is a cast of an address.

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.

getLow

public Expr getLow()

Return the low-level representation.

getInDataEdgeArray

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

getOutDataEdge

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

Specified by:

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 deletes this edge as an incoming edge. The two methods work together to maintain bi-directional edges.

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 Literal getConstantValue(HashMap<Expr,Literal> cvMap)

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

See Also:

Lattice

getConstantValue

public Literal getConstantValue()

Return the constant value of the expression. Do not follow use-def links.

See Also:

Lattice

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.

Parameters:

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

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

getCriticalChord

public final Chord getCriticalChord(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.

Parameters:

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

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

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.

removeUseDef

public abstract void removeUseDef()

Remove any 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 final 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. The right hand side of an assignment is considered to precede the left-hand side.

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

executionOrdinal

public int executionOrdinal()

Return the "execution ordinal" of this expression. Let o1 and o2 be the execution ordinals of two expressions e1 and e2 respectively. Then, o1 is less than o2 iff e1 is executed before e2. The right hand side of an assignment is considered to precede the left-hand side. Two expressions in the same expression tree will have the same ordinal.

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

See Also:

executionOrder(scale.score.expr.Expr), Chord.executionOrder(scale.score.chords.Chord), Scribble.labelCFG()

getLoopHeader

public final LoopHeaderChord getLoopHeader()

Return the node which represents the loop that contains this node.

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.

findLinearCoefficient

public int findLinearCoefficient(VariableDecl indexVar,
                                 LoopHeaderChord thisLoop)

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.

getAffineExpr

public final AffineExpr getAffineExpr(HashMap<Expr,AffineExpr> affines,
                                      LoopHeaderChord thisLoop)

Return the affine representation for this expression or null if it is not affine.

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

getAffineRepresentation

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

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

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

getDualExpr

public final DualExpr getDualExpr()

Return the DualExpr containing this SubscriptExpr or null if none. Follow the use-def chain if necessary.

getUseDef

public ExprChord getUseDef()

Return the use-def link for the expression. It's null for most expressions.

setUseDef

public void setUseDef(ExprChord se)

Set the use-def link for the expression. It's null for most expressions.

isMemRefExpr

public boolean isMemRefExpr()

Return true if the expression loads a value from memory.

isSimpleExpr

public boolean isSimpleExpr()

Return true if this is a simple expression. A simple expression consists solely of local scalar variables, constants, and numeric operations such as add, subtract, multiply, and divide.

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

This node is no longer needed so sever its use-def link, etc.

conditionalUnlinkExpression

public final void conditionalUnlinkExpression()

If the node is no longer needed, sever its use-def link, etc. A node is no longer needed if has no out-going data edge.

isLoopInvariant

public boolean isLoopInvariant(LoopHeaderChord loop)

Return true if this expression is loop invariant.

Parameters:

loop - is the loop

mayGenerateCall

public boolean mayGenerateCall()

Return true if this expression may result in the generation of a call to a subroutine.

findSubscriptExpr

public SubscriptExpr findSubscriptExpr()

Return the SubscriptExpr that this load uses or null if none is found. This method uses the use-def link to find an existing SubscriptExpr instance.

setTemporalReuse

public void setTemporalReuse(int level)

setCrossloopReuse

public void setCrossloopReuse(int level)

setSpatialReuse

public void setSpatialReuse(int level)

setStep

public void setStep(int step)

getReuseLevel

public int getReuseLevel()

containsDeclaration

public boolean containsDeclaration(Declaration decl)

Return true if this expression contains a reference to the variable.

See Also:

LoadExpr.setUseOriginal(boolean)

dependsOnDeclaration

public boolean dependsOnDeclaration(Declaration decl)

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

See Also:

LoadExpr.setUseOriginal(boolean)

optimizationCandidate

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

getAliasAnnote

public AliasAnnote getAliasAnnote()

Get the alias annotation associated with a Scribble operator. Most Scribble operators do not have alias variables so this routine may return null. Typically, the alias variable information is attached to the declaration node associated with the load operations. However, we sometimes need to create alias variables to hold alias information that is not directly assigned to a user variable (e.g., **x).

Returns:

the alias annotation associated with the expression

getDeclList

public abstract void getDeclList(java.util.AbstractCollection<Declaration> varList)

Add all declarations referenced in this expression to the Vector.

getLoadExprList

public abstract void getLoadExprList(Vector<LoadExpr> expList)

Add all LoadExpr instances in this expression to the Vector.

getExprList

public abstract void getExprList(Vector<Expr> expList)

Add all Expr instances in this expression to the Vector.

pushOperands

public abstract void pushOperands(Stack<Expr> wl)

Push all of the operands of this expression on the Stack.

replaceDecl

public abstract boolean replaceDecl(Declaration oldDecl,
                                    Declaration newDecl)

Replace all occurrances of a Declaration with another Declaration.

Returns:

true if a replace occurred.

recordRefs

public abstract void recordRefs(Chord stmt,
                                References refs)

Record any variable references in this expression in the table of references.

removeRefs

public abstract void removeRefs(Chord stmt,
                                References refs)

Remove any variable references in this expression from the table of references.

reduce

public Expr reduce()

Return a simplied equivalent expression. This method may modify the original expression. This is used in the lowering of subscript expressions.

See Also:

SubscriptExpr.lower()

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 Note

removeDualExprs

public boolean removeDualExprs()

Remove occurances of DualExpr instances.

Returns:

true if a DualExpr instance was removed.

addCast

public final Expr addCast(Expr orig)

Add a cast of an address if required. Optimizations often skip over address casts when finding applicable expressions. This adds those casts back in.

Parameters:

orig - is the expression being replaced

Returns:

the replacement expression of a cast of the replacement expression

addCast

public final Expr addCast(Type orig)

Add a cast of an address if required. Optimizations often skip over address casts when finding applicable expressions. This adds those casts back in.

Parameters:

orig - is the type of the expression being replaced

Returns:

the replacement expression of a cast of the replacement expression

hasTrueFalseResult

public boolean hasTrueFalseResult()

Return true if the result of the expression is either true (1) or false (0).