Current Alias Analysis
The Scale compile may perform alias analysis either:
This analysis may be performed by:
No alias analysis may also be selected in which case most Scale optimizations can not be performed.
- Bjarne Steensgaard's Algorithm
- a rich points-to set describes the variables
- interprocedural flow-insensitive analysis
- almost-linear time complexity
- linear space complexity
- based upon type-inference methods
- a Simple Algorithm which uses a single points-to set
Relevant Statements in Alias Analysis
x = y
x = &y
x = *y
x = op(y1, ... yn)
x = allocate(y)
*x = y
x = ftn(f1, ..., fn) => (r1, ..., rm)
x1, ..., xm = p(y1, ..., pn)
Storage Shape Graph
Type-based Alias Analysis
We are currently implementing another alias analysis method based upon types.
- Requires strongly typed language
- Typing rules, one for each relevant statement, define constraints needed to infer a set of types (for a program) that is conservative
- The alpha types describe values - a value type is a pair including a function type and a location type
- The tau types describe locations or pointers to locations
- The lambda types describe functions or pointers to functions
- All types are initialized to be bottom
Type Variable Productions
Type-based Alias Analysis Steps
- Assign each variable in the program a unique type variable
- Set each type variable to initially be
- Each statement in program is processed exactly once.
- Type variables are joined as necessary.
- Conditional joins permit a type variable with type to have a list of other types to join with should it become anything other than .
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.
Fred Chow, Sun Chan, Shin-Ming Liu, Raymond Lo and Mark Streich.
"Effective Representation of Aliases and Indirect Memory Operations in
SSA Form", In Compiler Construction, 6th International Conference,
CC'96, Linkoping, Sweden, Apr 1996.
Return to Scale dataflow diagram.
Return to Scale home page.
(Last changed: March 21, 2007.)