scale.score.analyses
Class FindAliases

java.lang.Object
  scale.score.pred.Supertype
      scale.score.pred.TraceChords
          scale.score.analyses.FindAliases

All Implemented Interfaces:

Predicate

public class FindAliases
extends TraceChords

This class visits nodes in order to compute aliases.

$Id: FindAliases.java,v 1.84 2007-10-04 19:58:20 burrill Exp $

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

We visit expression nodes and compute aliases when for each assignment operation. We expect that this predicate is used by the TraceChords predicate (which is responsible for idenitifing all expression nodes in a graph). The user may also provide a different technique for traversing the graph in order to find expression nodes.

We traversing the tree we sometimes need to create new temporary alias variables. For example, this happens when we compute some value that is not assigned to a temporary or real variable. We add the temporary alias variable as an annotation (AliasAnnote). When we are done using the temporary, we need to explictily remove it. At some point, we need to improve/fix the annotation code or use a different technique for saving the temporary alias variables.

The code to find the aliases depends on the structure of the Scribble tree. Any major changes to the structure must be reflected in this code.

See Also:

ExprChord

Field Summary

static boolean	classTrace True if traces are to be performed.
protected boolean	trace Set true to trace operation.

Fields inherited from class scale.score.pred.TraceChords

rl, thisChord, wl

Constructor Summary

FindAliases(AliasAnalysis analyzer, Suite suite, Aliases aliasesObject)
Create an object to find aliases in a scribble/score graph.

Method Summary

void	findAliases(RoutineDecl cn, Stack<Chord> wl) Find the aliases for the specified routine.
void	pointerExpression(Expr expr) A general routine that handles (potential) operations involving pointers.
void	visitArrayIndexExpr(ArrayIndexExpr e)
void	visitCallFunctionExpr(CallFunctionExpr e) Compute aliases at a function call node (FunctionCallOp.
void	visitCallMethodExpr(CallMethodExpr e) Compute aliases for method calls.
void	visitDualExpr(DualExpr e)
void	visitExpr(Expr expr) Handle expressions that may involve pointer values.
void	visitExprChord(ExprChord c) This is the main routine for handling aliases.
void	visitLiteralExpr(LiteralExpr e)
void	visitLoadDeclAddressExpr(LoadDeclAddressExpr e) Compute aliases at a LoadDeclAddressExpr node.
void	visitLoadDeclValueExpr(LoadDeclValueExpr e) Compute aliases at a LoadDeclValueExpr node.
void	visitLoadValueIndirectExpr(LoadValueIndirectExpr e) Compute aliases at a LoadValueIndirectExpr node.
void	visitSubscriptExpr(SubscriptExpr e)

Methods inherited from class scale.score.pred.TraceChords

getChord, setChord, visitChord

Methods inherited from class scale.score.pred.Supertype

visitAbsoluteValueExpr, visitAdditionExpr, visitAllocateExpr, visitAndExpr, visitBeginChord, visitBinaryExpr, visitBitAndExpr, visitBitComplementExpr, visitBitOrExpr, visitBitShiftExpr, visitBitXorExpr, visitBranchChord, visitCallExpr, visitCompareExpr, visitComplexValueExpr, visitConditionalExpr, visitConversionExpr, visitDecisionChord, visitDivisionExpr, visitEndChord, visitEqualityExpr, visitExitChord, visitExponentiationExpr, visitExprPhiExpr, visitFieldExpr, visitGotoChord, visitGreaterEqualExpr, visitGreaterExpr, visitIfThenElseChord, visitLeaveChord, visitLessEqualExpr, visitLessExpr, visitLoadExpr, visitLoadFieldAddressExpr, visitLoadFieldValueExpr, visitLoopExitChord, visitLoopHeaderChord, visitLoopInitChord, visitLoopPreHeaderChord, visitLoopTailChord, visitMarkerChord, visitMaxExpr, visitMinExpr, visitMultiplicationExpr, visitNaryExpr, visitNegativeExpr, visitNilExpr, visitNote, visitNotEqualExpr, visitNotExpr, visitNullChord, visitOrExpr, visitPhiExpr, visitPhiExprChord, visitRemainderExpr, visitReturnChord, visitSequentialChord, visitSubtractionExpr, visitSwitchChord, visitTernaryExpr, visitTranscendental2Expr, visitTranscendentalExpr, visitUnaryExpr, visitVaArgExpr, visitVaEndExpr, visitValueExpr, visitVarArgExpr, visitVaStartExpr, visitVectorExpr

Methods inherited from class java.lang.Object

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

Field Detail

classTrace

public static boolean classTrace

True if traces are to be performed.

trace

protected boolean trace

Set true to trace operation.

Constructor Detail

FindAliases

public FindAliases(AliasAnalysis analyzer,
                   Suite suite,
                   Aliases aliasesObject)

Create an object to find aliases in a scribble/score graph.

Parameters:

analyzer - the alias analysis algorithm.

suite - the suite containing the procedures in the program.

Method Detail

findAliases

public void findAliases(RoutineDecl cn,
                        Stack<Chord> wl)

Find the aliases for the specified routine.

visitCallFunctionExpr

public void visitCallFunctionExpr(CallFunctionExpr e)

Compute aliases at a function call node (FunctionCallOp. This method handles the case when the function returns void and there is no need for a store.

Specified by:

visitCallFunctionExpr in interface Predicate

Overrides:

visitCallFunctionExpr in class Supertype

visitCallMethodExpr

public void visitCallMethodExpr(CallMethodExpr e)

Compute aliases for method calls.

Specified by:

visitCallMethodExpr in interface Predicate

Overrides:

visitCallMethodExpr in class Supertype

visitLoadDeclAddressExpr

public void visitLoadDeclAddressExpr(LoadDeclAddressExpr e)

Compute aliases at a LoadDeclAddressExpr node. This method handles the case when we have &expr and the value is not directly stored anywhere. By directly stored, we mean that the LHS is a simple variable and does not involve any indirection. We need to create an alias variable to hold the result.

Specified by:

visitLoadDeclAddressExpr in interface Predicate

Overrides:

visitLoadDeclAddressExpr in class Supertype

visitLoadDeclValueExpr

public void visitLoadDeclValueExpr(LoadDeclValueExpr e)

Compute aliases at a LoadDeclValueExpr node. Most of the time this case is handled in visitStoreOp. However, we need to check for som special cases here.

We check for array loads that appear on the RHS. In this case, we treat the operation as the expression (&a[0]).

Specified by:

visitLoadDeclValueExpr in interface Predicate

Overrides:

visitLoadDeclValueExpr in class Supertype

See Also:

LoadDeclValueExpr

visitLoadValueIndirectExpr

public void visitLoadValueIndirectExpr(LoadValueIndirectExpr e)

Compute aliases at a LoadValueIndirectExpr node. This method handles the case when we have *expr and the value is not directly stored anywhere. By directly stored, we mean that the LHS is a simple variable and does not involve any indirection. We need to create an alias variable to hold the result.

Specified by:

visitLoadValueIndirectExpr in interface Predicate

Overrides:

visitLoadValueIndirectExpr in class Supertype

See Also:

LoadValueIndirectExpr

visitExprChord

public void visitExprChord(ExprChord c)

This is the main routine for handling aliases. We also create alias vars. in the other methods defined in this class when the expressions do not fit in the following cases:

• x = y
• x = *y
• x = &y
• *x = y
• x = op(y1,...,yN)
• x = malloc()
• x = func(p1,..,pN)
• r.f = y or x->f = y
• a[s] = y

The representation of these constructs in Scribble are different so each case must be handled separately.

Specified by:

visitExprChord in interface Predicate

Overrides:

visitExprChord in class Supertype

See Also:

ExprChord

visitExpr

public void visitExpr(Expr expr)

Handle expressions that may involve pointer values.

Overrides:

visitExpr in class Supertype

Parameters:

expr - the expression

visitLiteralExpr

public void visitLiteralExpr(LiteralExpr e)

Specified by:

visitLiteralExpr in interface Predicate

Overrides:

visitLiteralExpr in class Supertype

visitDualExpr

public void visitDualExpr(DualExpr e)

Specified by:

visitDualExpr in interface Predicate

Overrides:

visitDualExpr in class Supertype

visitSubscriptExpr

public void visitSubscriptExpr(SubscriptExpr e)

Specified by:

visitSubscriptExpr in interface Predicate

Overrides:

visitSubscriptExpr in class Supertype

visitArrayIndexExpr

public void visitArrayIndexExpr(ArrayIndexExpr e)

Specified by:

visitArrayIndexExpr in interface Predicate

Overrides:

visitArrayIndexExpr in class Supertype

pointerExpression

public void pointerExpression(Expr expr)

A general routine that handles (potential) operations involving pointers. For example, we need to track the addition of two pointer values. This method creates an alias variable for the generic expression op(y1,...,yN) that is not directly stored anywhere. By directly stored, we mean that the LHS is a simple variable and does not involve any indirection. We need to create an alias variable to hold the result.