- interprocedurally
- intraprocedurally
- never

- 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

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)

- 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

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

(