scale.score.expr
Class SubscriptExpr

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

All Implemented Interfaces:

AnnotationInterface, DisplayNode

public class SubscriptExpr
extends Expr

This class represents a subscript operation which computes an address of an array element (at a high-level).

$Id: SubscriptExpr.java,v 1.140 2007-10-17 13:40:01 burrill Exp $

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

Regardless of whether the source language uses row major or column major array ordering, the subscripts represented by this expression are always in row major (C style) ordering.

Field Summary

Fields inherited from class scale.score.expr.Expr

fpReorder, SE_DOMAIN, SE_NONE, SE_OVERFLOW, SE_STATE

Constructor Summary

SubscriptExpr(Type type, Expr array, Expr[] subscripts, Expr[] mins, Expr[] sizes)

Method Summary

boolean	addUse(Table<Declaration,SubscriptExpr> arraySubscripts) Add this SubscriptExpr to the table if it has a valid array reference.
void	addUses(java.util.AbstractCollection<Note> uses) Add all the uses of the address, specified by this SubscriptExpr instance, to the Vector.
void	addUses(java.util.AbstractCollection<Note> uses, Vector<Chord> dominated) Add all the uses of the address, specified by this SubscriptExpr instance, to the Vector.
Vector<LoopHeaderChord>	allRelatedLoops() Return loops whose indexes this subscript expression is using.
boolean	allSubscriptsOptimizationCandidates() Return true if all the subscripts of the subscript expression are optimization candidates.
boolean	containsDeclaration(Declaration decl) Return true if this expression contains a reference to the variable.
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	equivalent(Expr exp) Return true if the expressions are equivalent.
boolean	equivalentImp(Expr exp) Return true if the expressions are equivalent.
int	executionCostEstimate() Return a relative cost estimate for executing the expression.
SubscriptExpr	findSubscriptExpr() Return the SubscriptExpr that this load uses or null if none is found.
AliasAnnote	getAliasAnnote() Get the alias annotation associated with a Scribble operator.
Vector<Expr>	getArguments() Return a new vector with copies of the expression arguments.
Expr	getArray() Return the expression specifying the array.
void	getDeclList(java.util.AbstractCollection<Declaration> varList) Add all declarations referenced in this expression to the Vector.
Expr	getDimension(int i) Return the expression representing the dimension of the i-th subscript.
java.lang.String	getDisplayLabel() Return a String suitable for labeling this node in a graphical display.
void	getExprList(Vector<Expr> expList) Add all Expr instances in this expression to the Vector.
Expr	getIndexOrigin(int i) Return the expression representing the index origin of the i-th subscript.
void	getLoadExprList(Vector<LoadExpr> expList) Add all LoadExpr instances in this expression to the Vector.
Expr	getOperand(int position) Return the nth operand.
Expr[]	getOperandArray() Return an array of the operands to the expression.
Expr	getReference() Return the array associated with the subscript expression.
Expr	getSubscript(int i) Return the expression representing the i-th subscript.
Expr[]	getSubscripts() Return an enumeration of the subscripts of a subscript operator.
boolean	isDefined(Expr lv) The given expression is defined if the SubscriptExpr expression is defined and the given expression is the array.
boolean	isUse(Note arg) Return true if the argument is a use of the SubscriptExpr instance address.
void	loopClean() Clean up any loop related information.
Expr	lower() Lower the SubscriptExpr to an ArrayIndexExpr or AdditionExpr instance.
Expr	lowerIndex() Lower the SubscriptExpr to just the index calculation.
int	numOperands() Return the number of operands to this expression.
int	numSubscripts() Return the number of subscripts to the array.
boolean	optimizationCandidate() Return true if the expression can be moved without problems.
void	pushOperands(Stack<Expr> wl) Push all of the operands of this expression on the Stack.
void	recordRefs(Chord stmt, References refs) Record any variable references in this expression in the table of references.
protected void	removeOperand(int i) Allow some expressions such as VectorExpr to remove an operand.
void	removeRefs(Chord stmt, References refs) Remove any variable references in this expression from the table of references.
void	removeUseDef() Remove any use - def links, may - use links, etc.
boolean	replaceDecl(Declaration oldDecl, Declaration newDecl) Replace all occurrances of a Declaration with another Declaration.
void	setArray(Expr array) Set the array expression to this expression.
void	setDimension(Expr size, int i) Set the size of the specified dimension.
protected void	setOperand(Expr operand)
Expr	setOperand(Expr operand, int position) Set the nth operand of an expression.
void	setSubscripts(Expr index, int i) Set the index into the specified dimension.
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.
void	visit(Predicate p) Process a node by calling its associated routine.

Methods inherited from class scale.score.expr.Expr

addCast, addCast, canonical, changeInDataEdge, conditionalCopy, conditionalUnlinkExpression, deleteOutDataEdge, executionOrder, executionOrdinal, findCriticalChord, findLinearCoefficient, getAffineExpr, getAffineRepresentation, getCall, getConstantValue, getConstantValue, getCoreType, getCriticalChord, getDefExpr, getDisplayColorHint, getDisplayShapeHint, getDualExpr, getInDataEdge, getInDataEdgeArray, getLoopHeader, getLow, getLValue, getOutDataEdge, getPointedToCore, getReuseLevel, getRValue, getType, getUseDef, hasTrueFalseResult, isCast, isDefined, isLiteralExpr, isLoopInvariant, isMatchExpr, isMemoryDef, isMemRefExpr, isScalar, isSimpleExpr, mayGenerateCall, numInDataEdges, reduce, removeDualExprs, setCrossloopReuse, setOutDataEdge, setSpatialReuse, setStep, setTemporalReuse, setType, setUseDef, validate, 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

SubscriptExpr

public SubscriptExpr(Type type,
                     Expr array,
                     Expr[] subscripts,
                     Expr[] mins,
                     Expr[] sizes)

Parameters:

type - must be a PointerType

array - is the expression node holding address of array being subscripted

subscripts - is the vector of expressions representing array subscripts

mins - is the vector of expressions represnting the index origin for each dimension

sizes - is the vector of expressions representing the size for each dimension

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

getArray

public Expr getArray()

Return the expression specifying the array.

numSubscripts

public int numSubscripts()

Return the number of subscripts to the array.

getSubscript

public Expr getSubscript(int i)

Return the expression representing the i-th subscript.

getIndexOrigin

public Expr getIndexOrigin(int i)

Return the expression representing the index origin of the i-th subscript.

getDimension

public Expr getDimension(int i)

Return the expression representing the dimension of the i-th subscript.

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

isDefined

public boolean isDefined(Expr lv)

The given expression is defined if the SubscriptExpr expression is defined and the given expression is the array.

Overrides:

isDefined in class Expr

Parameters:

lv - the expression reprsenting the array name

Returns:

true if the array is defined.

getReference

public Expr getReference()

Return the array associated with the subscript expression. We use the array name to represent the access of the array - instead of the array index value.

Overrides:

getReference in class Expr

Returns:

null since a general expression doesn't have a variable

getOperandArray

public final Expr[] getOperandArray()

Return an array of the operands to the expression.

Specified by:

getOperandArray in class Expr

setArray

public void setArray(Expr array)

Set the array expression to this expression.

setDimension

public void setDimension(Expr size,
                         int i)

Set the size of the specified dimension.

Parameters:

size - is the new dimension size

i - specifies the dimension

setSubscripts

public void setSubscripts(Expr index,
                          int i)

Set the index into the specified dimension.

Parameters:

index - is the new dimension index

i - specifies the dimension

setOperand

protected void setOperand(Expr operand)

setOperand

public Expr setOperand(Expr operand,
                       int position)

Description copied from class: Expr

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.

Overrides:

setOperand in class Expr

Parameters:

operand - - the new operand

position - - indicates which operand

Returns:

the previous operand

numOperands

public int numOperands()

Return the number of operands to this expression.

Specified by:

numOperands in class Expr

getOperand

public final Expr getOperand(int position)

Return the nth operand.

Overrides:

getOperand in class Expr

Parameters:

position - the index of the operand

removeOperand

protected void removeOperand(int i)

Allow some expressions such as VectorExpr to remove an operand.

getArguments

public Vector<Expr> getArguments()

Return a new vector with copies of the expression arguments.

equivalentImp

public boolean equivalentImp(Expr exp)

Return true if the expressions are equivalent. Assume subscripts are AffineExpr expressions. This method should be called by the equivalentImp() method of any derived classes.

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.

Overrides:

equivalent in class Expr

Returns:

true if classes are identical and the core types are equivalent

getSubscripts

public Expr[] getSubscripts()

Return an enumeration of the subscripts of a subscript operator.

addUse

public boolean addUse(Table<Declaration,SubscriptExpr> arraySubscripts)

Add this SubscriptExpr to the table if it has a valid array reference. A valid subscript expression is one that dependence testing can utilize. Examples of invalid subscript expressions include

   (func(a,b))[i]
   strct.arr[i]
 

Returns:

true if valid use

addUses

public void addUses(java.util.AbstractCollection<Note> uses)

Add all the uses of the address, specified by this SubscriptExpr instance, to the Vector. The uses are obtained by following the use-def links.

See Also:

isUse(scale.score.Note)

addUses

public void addUses(java.util.AbstractCollection<Note> uses,
                    Vector<Chord> dominated)

Add all the uses of the address, specified by this SubscriptExpr instance, to the Vector. The CFG nodes of uses must be in the dominated list. The uses are obtained by following the use-def links.

See Also:

isUse(scale.score.Note)

isUse

public boolean isUse(Note arg)

Return true if the argument is a use of the SubscriptExpr instance address.

See Also:

addUses(java.util.AbstractCollection)

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 Expr

allRelatedLoops

public Vector<LoopHeaderChord> allRelatedLoops()

Return loops whose indexes this subscript expression is using. No assumption should be made concerning the order that the loops are placed in the result.

lower

public Expr lower()

Lower the SubscriptExpr to an ArrayIndexExpr or AdditionExpr instance. Lowering may result in a sequence of CFG nodes as well as the lowered expression. These nodes are appended to the supplied vector in the order in which they should be in the CFG. Also, some temporary variables may be created to hold intermediate results. These new variable declarations are added to the supplied vector.

lowerIndex

public Expr lowerIndex()

Lower the SubscriptExpr to just the index calculation. Lowering may result in a sequence of CFG nodes as well as the lowered expression. These nodes are appended to the supplied vector in the order in which they should be in the CFG. Also, some temporary variables may be created to hold intermediate results. These new variable declarations are added to the supplied vector.

loopClean

public void loopClean()

Clean up any loop related information.

Overrides:

loopClean in class Expr

unlinkExpression

public void unlinkExpression()

If the node is no longer needed, sever its use-def link, etc.

Overrides:

unlinkExpression in class Expr

containsDeclaration

public boolean containsDeclaration(Declaration decl)

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

Overrides:

containsDeclaration in class Expr

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.

Overrides:

dependsOnDeclaration in class Expr

See Also:

LoadExpr.setUseOriginal(boolean)

allSubscriptsOptimizationCandidates

public boolean allSubscriptsOptimizationCandidates()

Return true if all the subscripts of the subscript expression are optimization candidates.

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. For a SubscriptExpr instance return false. Array accesses must be optimized using data dependence testing.

Specified by:

optimizationCandidate in class Expr

See Also:

ScalarReplacement

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

Overrides:

findSubscriptExpr in class Expr

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

Overrides:

getAliasAnnote in class Expr

Returns:

the alias annotation associated with the expression

getDeclList

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

Add all declarations referenced in this expression to the Vector.

Specified by:

getDeclList in class Expr

getLoadExprList

public void getLoadExprList(Vector<LoadExpr> expList)

Add all LoadExpr instances in this expression to the Vector.

Specified by:

getLoadExprList in class Expr

getExprList

public void getExprList(Vector<Expr> expList)

Add all Expr instances in this expression to the Vector.

Specified by:

getExprList in class Expr

pushOperands

public void pushOperands(Stack<Expr> wl)

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

Specified by:

pushOperands in class Expr

replaceDecl

public boolean replaceDecl(Declaration oldDecl,
                           Declaration newDecl)

Replace all occurrances of a Declaration with another Declaration. Return true if a replace occurred.

Specified by:

replaceDecl in class Expr

Returns:

true if a replace occurred.

removeUseDef

public void removeUseDef()

Remove any use - def links, may - use links, etc.

Specified by:

removeUseDef in class Expr

recordRefs

public void recordRefs(Chord stmt,
                       References refs)

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

Specified by:

recordRefs in class Expr

removeRefs

public void removeRefs(Chord stmt,
                       References refs)

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

Specified by:

removeRefs in class Expr

executionCostEstimate

public int executionCostEstimate()

Return a relative cost estimate for executing the expression.

Specified by:

executionCostEstimate in class Note

sideEffects

public int sideEffects()

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

Specified by:

sideEffects in class Expr

See Also:

Expr.SE_NONE