scale.alias.shapirohorowitz
Class ShapiroHorowitz

java.lang.Object
  scale.alias.AliasAnalysis
      scale.alias.shapirohorowitz.ShapiroHorowitz

public class ShapiroHorowitz
extends AliasAnalysis

A class which implements extension to Bjarne Steensgaard's alias analysis algorithm.

$Id: ShapiroHorowitz.java,v 1.19 2005-06-15 04:17:05 asmith Exp $

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

The algorithm performs interprocedural flow-insensitive points-to analysis. The important features of the algorithm are:

• It runs in almost linear time.
• It is based on type inference methods.
• types can point off to multiple types - upto k of them (assuming k categories)

Field Summary

Fields inherited from class scale.alias.AliasAnalysis

classTrace, trace

Constructor Summary

ShapiroHorowitz(boolean interprocedural, int numberCategories)
Create an instance of the Shapiro-Horwitz alias analysis algorithm and indicate if it operates on the whole program.

ShapiroHorowitz(int numberCategories)
Create an instance of the Shapiro-Horwitz alias analysis algorithm.

Method Summary

void	addrAssign(AliasVar lhs, AliasVar addr) Inference rule for the assignment of an address (x = &y).
AliasVar	addVariable(Declaration decl) Add a variable that needs to be processed by the algorithm.
AliasVar	addVariable(Declaration decl, AliasVar v) Add a variable into the analyzer and indicate the variable is in the same alias group as another variable.
void	assignPtr(AliasVar ptr, AliasVar rhs) Inference rule for assigning to a pointer (*x = y).
void	cleanup() Remove all the un-needed stuff.
void	functionCall(AliasVar lhs, AliasVar func, Vector<AliasVar> args) Inference rule for a function call assignment.
void	functionDef(AliasVar func, Vector<AliasVar> params, AliasVar retval) Inference rule for a function definition.
void	heapAssign(AliasVar lhs) Inference rule for assigning dynamically allocated memory.
boolean	isContextSensitive() Return false because Shapiro-Horwitz's algorithm is not context sensitive.
boolean	isFlowSensitive() Return false because Shapiro-Horwitz's algorithm is not flow sensitive.
boolean	isInterProcedural() Return true if the analysis is interprocedural.
void	opAssign(AliasVar lhs, Vector<AliasVar> opnds) Inference rule for an operation (x = op(y1,…,yN)).
void	ptrAssign(AliasVar lhs, AliasVar ptr) Inference rule for a pointer assignment (x = *y
void	simpleAssign(AliasVar lhs, AliasVar rhs) Inference rules for simple assignment (x = y).

Methods inherited from class java.lang.Object

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

Constructor Detail

ShapiroHorowitz

public ShapiroHorowitz(int numberCategories)

Create an instance of the Shapiro-Horwitz alias analysis algorithm.

ShapiroHorowitz

public ShapiroHorowitz(boolean interprocedural,
                       int numberCategories)

Create an instance of the Shapiro-Horwitz alias analysis algorithm and indicate if it operates on the whole program.

Parameters:

interprocedural - set to true if the analysis should be interprocedural

Method Detail

isFlowSensitive

public boolean isFlowSensitive()

Return false because Shapiro-Horwitz's algorithm is not flow sensitive.

Specified by:

isFlowSensitive in class AliasAnalysis

Returns:

false

isContextSensitive

public boolean isContextSensitive()

Return false because Shapiro-Horwitz's algorithm is not context sensitive.

Specified by:

isContextSensitive in class AliasAnalysis

Returns:

false

isInterProcedural

public boolean isInterProcedural()

Return true if the analysis is interprocedural. We can parameterize Shapiro-Horwitz's algorithm to work on a single procedure or the entire program.

Specified by:

isInterProcedural in class AliasAnalysis

addVariable

public AliasVar addVariable(Declaration decl)

Add a variable that needs to be processed by the algorithm. We create a unique non-standard type for the variable and add it to the fast union/find data structure.

Specified by:

addVariable in class AliasAnalysis

Parameters:

decl - is the name of the variable.

Returns:

our alias representation of the varaible.

addVariable

public AliasVar addVariable(Declaration decl,
                            AliasVar v)

Add a variable into the analyzer and indicate the variable is in the same alias group as another variable. information from the given alias variable.

Specified by:

addVariable in class AliasAnalysis

Returns:

the alias variable that represents the varaible.

simpleAssign

public void simpleAssign(AliasVar lhs,
                         AliasVar rhs)

Inference rules for simple assignment (x = y).

Specified by:

simpleAssign in class AliasAnalysis

Parameters:

lhs - the left hand side of the assignment.

rhs - the right hand side of the assignment.

addrAssign

public void addrAssign(AliasVar lhs,
                       AliasVar addr)

Inference rule for the assignment of an address (x = &y).

Specified by:

addrAssign in class AliasAnalysis

Parameters:

lhs - the left hand side of the assignment.

addr - the right hand side of the assignment (the address).

ptrAssign

public void ptrAssign(AliasVar lhs,
                      AliasVar ptr)

Inference rule for a pointer assignment (x = *y

Specified by:

ptrAssign in class AliasAnalysis

Parameters:

lhs - the left hand side of the assignment.

ptr - the right hand side of the assignment (the pointer).

opAssign

public void opAssign(AliasVar lhs,
                     Vector<AliasVar> opnds)

Inference rule for an operation (x = op(y1,…,yN)).

Specified by:

opAssign in class AliasAnalysis

Parameters:

lhs - the left hand side of the assignment.

opnds - the list of arguments of the operation.

heapAssign

public void heapAssign(AliasVar lhs)

Inference rule for assigning dynamically allocated memory.

Specified by:

heapAssign in class AliasAnalysis

Parameters:

lhs - the left hand side of the assignment.

assignPtr

public void assignPtr(AliasVar ptr,
                      AliasVar rhs)

Inference rule for assigning to a pointer (*x = y).

Specified by:

assignPtr in class AliasAnalysis

Parameters:

ptr - the pointer representing the left hand side of the assignment.

rhs - the right hand side of the assignment.

functionDef

public void functionDef(AliasVar func,
                        Vector<AliasVar> params,
                        AliasVar retval)

Inference rule for a function definition.

Specified by:

functionDef in class AliasAnalysis

Parameters:

func - the alias variable representing the function.

params - the alias variables representing the list of parameters.

retval - the alias variables representing the return value.

functionCall

public void functionCall(AliasVar lhs,
                         AliasVar func,
                         Vector<AliasVar> args)

Inference rule for a function call assignment.

Specified by:

functionCall in class AliasAnalysis

Parameters:

lhs - the alias variables representing the value returned by the function call (is null if there function returns nothing)

func - the alias variables representing the function.

args - alias variables representing the arguments.

cleanup

public void cleanup()

Remove all the un-needed stuff.