scale.alias.steensgaard
Class Steensgaard

java.lang.Object
  scale.alias.AliasAnalysis
      scale.alias.steensgaard.Steensgaard

public class Steensgaard
extends AliasAnalysis

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

$Id: Steensgaard.java,v 1.41 2005-05-09 17:10:34 burrill Exp $

Copyright 2008 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.

Field Summary

Fields inherited from class scale.alias.AliasAnalysis

classTrace, trace

Constructor Summary

Steensgaard()
Create an instance of the Steensgaard alias analysis algorithm.

Steensgaard(boolean ip)
Create an instance of the Steensgaard alias analysis algorithm and indicate if it operates on the whole program.

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	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 Steensgaard's algorithm is not context sensitive.
boolean	isFlowSensitive() Return false because Steensgaard'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

Steensgaard

public Steensgaard()

Create an instance of the Steensgaard alias analysis algorithm.

Steensgaard

public Steensgaard(boolean ip)

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

Parameters:

ip - set to true if the analysis should be interprocedural

Method Detail

isFlowSensitive

public boolean isFlowSensitive()

Return false because Steensgaard's algorithm is not flow sensitive.

Specified by:

isFlowSensitive in class AliasAnalysis

Returns:

false

isContextSensitive

public boolean isContextSensitive()

Return false because Steensgaard'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 Steensgaard'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.