Package scale.alias.steensgaard

Provides alias analysis using Steensgaard's algorithm.

See:
Description

Class Summary

AliasType	A class which implements the non-standard set of types used in Steensgaard's algorithm to represent abstract locations.
ECR	A class which represents an Equivalence Class Representative (ECR) with associated type information.
FunctionType	A class which implements the non-standard type describing functions (or pointers to functions).
LocationType	A class which implements the non-standard type describing locations (or pointers to locations).
Steensgaard	A class which implements Bjarne Steensgaard's alias analysis algorithm.
TypeVar	A class which represents a type variable in Steensgaard's alias analysis algorithm.
ValueType	A class which implements the non-standard type describing values.

Package scale.alias.steensgaard Description

Provides alias analysis using Steensgaard's algorithm.

Basically, Steensgaard's analysis context-insensitive (meaning it doesn't care about function call paths and scoping) and flow-insensitive (meaning it doesn't care about statement ordering). This means that the analysis produces a (sometimes very) conservative result. The analysis doesn't operate on names - instead we assign types to names and operate on the types. At the beginning of the analysis there is a one-to-one correspondence between names and types. The algorithm merges the types during the analysis and at the end, a single type may represent many names. The type is a representation of the alias characteristics of the program. The use of types in the algorithm is a little confusing because they are not based upon real programming language types. The reason is that the algorithm is based upon type inference algorithms.

For example, if we have the following program:

int *g;
void foo() {
 int b;
 g = &b;
 ...
}
void bar() {
 int a;
 g = &a;
 ...
}

Then, after the analysis, it appears that g -> {a,b} (g points to a and b), meaning that *g, a, b are aliases of each other. Of course, if we look at the program, a and b can never be alias because they appear in different scopes but Steensgaard's analysis does not recognize this. But, if say, bar() is defined as:

void bar() {
  int a,b;
  g = &a;
  ...
}

Then, the analysis would still have g -> {a,b} BUT the b is the local variable from foo, not the local variable from bar. (It may be easier to see this if we prepend the names with the scopes. Thus, File_g -> {File_Bar_a, File_Foo_b}).

Actually, Steensgaard's analysis doesn't care about names. It assigns alias variables or types to each name and uses those during the analysis. The alias variables represent the alias characteristics of the program. Before analysis we assign the alias variables to all globals, function names, and local variable names.

g (global) = AV1; (AV = alias variable)
a (in bar) = AV2;
b (in foo) = AV3;
b (in bar) = AV4;

After the analysis, we have: AV1 -> {AV2, AV3} (this doesn't quite follow the implementation as we have left out some details).

Most of our optimizations don't care about names while performing transformations. They follow the use-def links. In fact, the only reason we added the name to an alias variable is for debugging. But, if you need to determine if two variables are aliases, then you need to get the declaration for the variables and obtain the alias variable for the declarations.

Bjarne Steensgaard, "Points-to Analysis in Almost Linear Time", Proceedings of the Twenty Third Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St. Petersburg, FL, Jan 1996.